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

额外空间复杂度为O（1），不能开辟另一个数组。

过程图解：

public class NetherLandsFlag {
    public static int[] partition(int[] arr,int left,int right,int target){
        int less = left - 1;        //  ＜区的区域
        int more = right + 1;       //  ＞区的区域

        while (left < more){        //left表示当前值
            if (arr[left] < target){
                swap(arr,++less,left++);    //＜区扩张，当前值增加
            }else if (arr[left] > target){
                swap(arr,--more,left);      //大于区缩小，交换，当前值不变
            }else {
                left++;              //相等，当前值增加
            }
        }
        int[] res = {less + 1, more - 1};
        return res;     //返回相等区域的左右边界。
    }

    public static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

 

版权声明：本文为pxy-1999原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://www.cnblogs.com/pxy-1999/p/13304465.html