給定一個(gè)數(shù)組arr互订，和一個(gè)數(shù)num吱肌，請(qǐng)把小于num的數(shù)放在數(shù)組的左邊，等于num的數(shù)放在數(shù)組的中間仰禽，大于num的數(shù)放在數(shù)組的右邊氮墨。
要求額外空間復(fù)雜度O(1)，時(shí)間復(fù)雜度O(N)

解決思想（分治法）：

1. 我們想象在數(shù)組的兩邊各存在一個(gè)區(qū)域吐葵，一個(gè)是“小于”區(qū)规揪，一個(gè)是“大于”區(qū)≌哿“小于”區(qū)在數(shù)組的最左邊粒褒，“大于”區(qū)在數(shù)組的最右邊识颊。
2. 一開(kāi)始這兩個(gè)區(qū)域都不存在數(shù)诚镰，所以我們將小于區(qū)的下標(biāo)設(shè)置為-1，大于區(qū)域的下標(biāo)設(shè)置為數(shù)組的長(zhǎng)度加1祥款。
3. 從下標(biāo)0開(kāi)始清笨，比較數(shù)組里的數(shù)和num的大小。如果當(dāng)前位置上的數(shù)小于num刃跛，就將其放在小于區(qū)域抠艾；如果等于num則不動(dòng)，繼續(xù)比較下一個(gè)數(shù)字桨昙；如果大于num检号，就將其放在大于區(qū)域。
4. 在當(dāng)前下標(biāo)遇到大于區(qū)域時(shí)蛙酪，整個(gè)流程結(jié)束齐苛。
   此時(shí)，小于區(qū)域在左邊桂塞，等于區(qū)域在中間凹蜂，大于區(qū)域在右邊。

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) { //當(dāng)前數(shù)和大于區(qū)域撞上時(shí)，停止流程
            if (arr[L] < num) { //如果當(dāng)前數(shù)小于num
                // 將當(dāng)前數(shù)和“小于”區(qū)域的下一個(gè)數(shù)進(jìn)行交換
                // 同時(shí)“小于”區(qū)域下標(biāo)加1玛痊，當(dāng)前下標(biāo)加1汰瘫，繼續(xù)判斷下一個(gè)數(shù)
                swap(arr, ++less, L++);
            } else if (arr[L] > num) { //如果當(dāng)前數(shù)大于num
                // 將當(dāng)前數(shù)和“大于”區(qū)域的前一個(gè)數(shù)x進(jìn)行交換
                // 同時(shí)“大于”區(qū)域下標(biāo)減1，當(dāng)前下標(biāo)不變擂煞，開(kāi)始判斷x和num的大小
                swap(arr, --more, L);
            } else { //當(dāng)前等于num混弥，當(dāng)前下標(biāo)加1，繼續(xù)判斷下一個(gè)數(shù)
                L++;
            }
        }
        return new int[] { less + 1, more - 1 }; // 返回“等于”區(qū)域的左邊界对省、右邊界的下標(biāo)
    }

    // 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]);
    }
}