算法之荷兰国旗问题

题目一：
给定一个数组arr，和一个数num，请把小于等于num的数放在数组的左边，大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(n)。
分析：遍历数组，只要比num小的，往左排，比num大的，跳过本次操作，这样看来，我们只需要交换满足条件的元素便可以实现题目的要求了。首先我们先建立一个在数组边界外的指针。数组从L至R进行遍历，那么我们的指针当前的位置为index = L-1，在遍历过程中和给定条件进行比较，如满足条件，则交换位置，且index向右移动指针。

代码

public class SortAssignArray {

    public static void sort(int[]arr,int num) {
        if(arr == null || arr.length<2) {
            return;
        }
        int index = -1;  //遍历数组从0开始，那么当前指针的左边界就是-1；
        for(int i=0;i<arr.length;i++) {
            if(arr[i]<=num) {
                swap(arr, ++index, i);  //满足条件交换位置，且index向右移动
            }else {
                continue;
            }
        }
    }
    //交换函数
    public static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    public static void main(String[]args) {
        int []arr  = {2,1,8,5,3,9,7,4,10};
        int num = 6;
        sort(arr, num);
        System.out.println(Arrays.toString(arr));
    }
}

荷兰国旗问题是面试中经常遇到的算法考题，一起来看题目要求并分析题目求解过程。
问题2：给定一个数组arr，和一个数num，请把小于num的数放在数组的左边，等于num的数组的中间，大于num的数放在数组的右边。
要求额外空间复杂度O(1),时间复杂度O(n)
这道题和上述的题目有些相似，唯一不同的是加了个等于num放中间这个条件，其实如果你理解了上述的题目的含义，这道题也不难理解了。解这道题需要将数组划分为3部分，即小于num、等于num、大于num，这样一来我们建立三个索引，分别是左边界的，当前位置索引，右边界的索引，通过移动索引并交换位置即可得到答案。

代码

import java.util.Arrays;

//荷兰国旗问题
public class NetherlandsFlag {
    
    public static int[] partition(int[]arr,int L,int R,int num) {
        int less = L - 1;  //左边界的索引
        int more = R + 1;  //右边界的索引
        int cur = L;  //当前位置的索引
        while(cur < more) {
            if(arr[cur] < num) {
                swap(arr, ++less, cur++);
            }else if(arr[cur] > num) {
                swap(arr, --more, cur);// cur不自加的原因是交换后的arr[cur]可能等于num，也可能小于，或者是大于，需要再做一次判断
            }else {  
                cur++;
            }
        }
        return new int[] {less+1,more-1};
    }
    
    public static void swap(int [] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
    
    public static void main(String[] args) {
        int[] arr = {23,4,2,5,7,42,34,32,7,8,39,45,63,21};
        int num = 34;
        partition(arr, 0, arr.length-1, num);
        System.out.println(Arrays.toString(arr));
    }
}