荷兰国旗问题

小鱼儿 2023-01-16 06:17 134阅读 0赞

# 一、问题描述 #

荷兰国旗问题，顾名思义，就是按照荷兰国旗的形式，给定一个数 x ，将 < x 的数放到左边，=x 的数放中间，>x 的数放右边，将数组中的元素分成三块，有的时候可能要求 <= x 的放左边：

![8bbb4465dcf6f2f43d5c0857eed8d14d.png][]

# 二、解题思路 #

首先，数组是无序的，如果要求 <= x 放左边，>x 的放右边，将数组分成两部分，该如何做？

基本思路就是将**元素遍历**，与 x 比较大小，通过交换将元素放到对应区域中。

我们应当在数组的左边设定一个指针，指针位置以左（包括指针位置），代表 <=x 的区域，可以称为 less 区。

然后再设定一个代表当前遍历元素的**遍历指针 **，若当前元素 <=x，就将其与 less 区的下一个数交换，然后 less 区右扩一位。遍历指针右移；若当前元素 >x，那么遍历指针直接右移。

![watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Zyj5paX5aOrTW9ydHk_size_16_color_FFFFFF_t_70_g_se_x_16][]

如果要求 <x 放左，=x 放中间，>x 放右，将数组分成三部分，该如何做？

按照上面的思路，分别在数组两侧设置一个 <x 的 less 区和 >x 的 more 区，再设置一个遍历指针指向当前遍历的位置。

另外，如果给定数列不是在整个范围内划分荷兰国旗区域，而是给定了操作区间，那么区间头和尾的位置应该给定，如  L 和 R。

从 L 位置开始遍历，如果**当前数 <x** ，当前数与less区下一个数交换，less 区右扩，遍历指针右移；如果**当前数 =x**，当前数直接跳下一个；如果**当前数>x**，当前数与 more区前一个数交换，more 区左移，遍历指针不动，因为刚刚从右边交换过来的数还需要再比较一次。

这样重复上面的步骤，如果当前指针与more区位置重合（即 while(curr < more)才执行循环 ），那么停止操作。

# 三、完整代码 #

以分成三部分的题目为例，完整代码如下：

public static int[] netherlandsFlag(int[] arr, int L, int R, int target) {
            if (L > R)
                return new int[]{-1, -1};
            if (L == R)
                return new int[]{L, R};
            int less = L - 1;
            int more = R + 1;
            int curr = L;
            while (curr < more) {
                if (arr[curr] == target) {
                    curr++;
                } else if (arr[curr] < target) {
                    SortUtil.swap(arr, curr, less + 1);
                    less++;
                    curr++;
                } else {
                    SortUtil.swap(arr, curr, more - 1);
                    more--;
                }
            }
            return new int[]{less + 1, more};
        }

# 四、时间复杂度 #

在整个数组的划分过程中，比较、交换，以及赋值操作都是常数时间，在估算时间复杂度时可以忽略。

而在while循环中，我们也没有任何回退动作，从左到右一次遍历所有元素，因此，上面的代码时间复杂度是**O(N)**。

[8bbb4465dcf6f2f43d5c0857eed8d14d.png]: /images/20221022/4c7fb439a81740adafb8246d00ed20fd.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Zyj5paX5aOrTW9ydHk_size_16_color_FFFFFF_t_70_g_se_x_16]: /images/20221022/a0935765818b4ed7964da556838bd071.png