625.Partition Array II

1.Description(Medium)

Partition an unsorted integer array into three parts:

1. The front part < low

2. The middle part >= low & <= high3.

   3.The tail part > high

Return any of the possible solutions.

Notice

low <= high in all test cases.

Example

Given[4,3,4,1,2,3,1,2], and low =2and high =3.

Change to[1,1,2,3,2,3,4,4].

([1,1,2,2,3,3,4,4] is also a correct answer, but [1,2,1,2,3,3,4,4] is not)

Challenge

1. Do it in place.

2. Do it in one pass (one loop).

2.Code

跟sort colors II 非常相似，只不过sort color II 里面的上下限需要不断变化，这个题目是固定的low high

在代码里的变化就是sort colors II 在while(i<=right)外层还有一个while(min<max)的一层，在这一层里，控制最后结束时i要变回当前left的位置，以及min 和max的变化。

 public void partition2(int[] nums, int low, int high) {
        if(nums==null || nums.length==0){
            return;
        }
        int left=0;
        int right=nums.length-1;
        int i=0;
        while(i<=right){
            if(nums[i]<low){
                swap(nums,i,left);
                i++;
                left++;               
            }
            else if(nums[i]>high){
                swap(nums,i,right);
                right--;
            }else{
                i++;
            }
        }
    }

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