数据结构与算法：荷兰国旗问题

荷兰国旗

荷兰国旗问题：简单来说就是，我们以一个数num作为基准，将一个数组划分为左侧为小于num的部分，右侧为大于num的部分，中间为等于num的部分。
假设一个数组为4 3 7 6 5 2 5，且num=5，以此来划分，最终数组被划分为左侧小于5，中间等于5，右侧大于5。像这样：4 3 2 5 5 6 7 。需要注意的是经过这样划分后的数组不一定是有序的。

如何划分

假设我们需要对L 到 R 的序列区间变成满足荷兰国旗描述的序列区间，我们需要先准备 less 指针和 more 指针分别指向 L 的左侧和 R 的右侧。cur指针指向 L 。less 指向的区域为小于 num的区域， more 指向的区域为大于 num 的区域。如下图示：

图片1.png

从 cur 当前指向的位置开始，将其指向的数与 num (num = 5) 进行比较。如果该数小于 num ，则 cur 指向的数就与 less 区域的后一个数比较，并且less指针加一，cur 指向下一个数；如果该数等于 num， 则 cur 指针直接指向下一个位置；如果该数大于 num ，则 cur 指向的数就与 more 区域的前一个数比较，并且 more 指针减一。一直重复这样的划分操作指导 cur 指针与 more 相遇为止。

图片2.png

伪代码描述

while(cur < more){
if(当前数 = num) cur++
if(当前数 < num) 和小于区域后一个数交换，less++,cur++
if(当前是 > num) 和大于区域前一个数交换，more--
}

完整代码

public static int[] partition(int[] arr,int left,int right,int num) {
        
            //if(arr == null) return null;
            
            int less = left - 1;
            int more = right + 1;
            int current = left;
            
            while(current < more) {
                if(arr[current] < num) {
                    swap(arr,less+1,current);
                    less++;
                    current++;
                }else if(arr[current] > num) {
                    swap(arr,more-1,current);
                    more--;
                }else {
                    current++;
                }
                
            }
        
        
        return new int[] {less+1,more};
    }
    
    private static void swap(int[] arr,int i,int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }