荷兰国旗问题

给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数放在数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1)，时间复杂度O(N)

解决思想（分治法）：

我们想象在数组的两边各存在一个区域，一个是“小于”区，一个是“大于”区。“小于”区在数组的最左边，“大于”区在数组的最右边。
一开始这两个区域都不存在数，所以我们将小于区的下标设置为-1，大于区域的下标设置为数组的长度加1。
从下标0开始，比较数组里的数和num的大小。如果当前位置上的数小于num，就将其放在小于区域；如果等于num则不动，继续比较下一个数字；如果大于num，就将其放在大于区域。
在当前下标遇到大于区域时，整个流程结束。
此时，小于区域在左边，等于区域在中间，大于区域在右边。

Java代码如下：

public class NetherlandsFlag {

    public static int[] partition(int[] arr, int L, int R, int num) {
        int less = L - 1;
        int more = R + 1;
        while (L < more) { //当前数和大于区域撞上时，停止流程
            if (arr[L] < num) { //如果当前数小于num
                // 将当前数和“小于”区域的下一个数进行交换
                // 同时“小于”区域下标加1，当前下标加1，继续判断下一个数
                swap(arr, ++less, L++);
            } else if (arr[L] > num) { //如果当前数大于num
                // 将当前数和“大于”区域的前一个数x进行交换
                // 同时“大于”区域下标减1，当前下标不变，开始判断x和num的大小
                swap(arr, --more, L);
            } else { //当前等于num，当前下标加1，继续判断下一个数
                L++;
            }
        }
        return new int[] { less + 1, more - 1 }; // 返回“等于”区域的左边界、右边界的下标
    }

    // for test
    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }

    // for test
    public static int[] generateArray() {
        int[] arr = new int[10];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = (int) (Math.random() * 3);
        }
        return arr;
    }

    // for test
    public static void printArray(int[] arr) {
        if (arr == null) {
            return;
        }
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] test = generateArray();
        printArray(test);
        int[] res = partition(test, 0, test.length - 1, 1);
        printArray(test);
        System.out.println(res[0]);
        System.out.println(res[1]);
    }
}

最后编辑于：2019.10.30 18:32:45