148.Sort Colors

1.Description(Medium)

Given an array withn_objects colored_red,white_or_blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers0,1, and2to represent the color red, white, and blue respectively.

Notice

You are not suppose to use the library's sort function for this problem. You should do it in-place (sort numbers in the original array).

Example

Given[1, 0, 1, 2], sort it in-place to[0, 1, 1, 2]

Challenge

A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0's, 1's, and 2's, then overwrite array with total number of 0's, then 1's and followed by 2's.

Could you come up with an one-pass algorithm using only constant space?

2.Code

一开始想到的就是计数排序，但是计数排序需要两边扫描，第一遍统计红，白，蓝的数目，第二遍生成新数组。

考虑到题目要求one pass。这就意味着类似于链表的双指针问题，这里也要track两个index，一个是red的index，一个是blue的index，两边往中间走。

i从0到blue index扫描，

遇到0，放在red index位置，red index后移；

遇到2，放在blue index位置，blue index前移；

遇到1，i后移。

扫描一遍得到排好序的数组。时间O(n)，空间O(1)

 public void sortColors(int[] nums) {
        if(nums==null || nums.length==0){
            return;
        }
        int redindex=0;
        int blueindex=nums.length-1;
        int i=0;
        //注意这里是<=
        while(i<=blueindex){
            if(nums[i]==0){
                swap(nums,redindex,i);
                redindex++;
                i++;
            }
            else if(nums[i]==2){
                swap(nums,blueindex,i);
                blueindex--;
            }
            else if(nums[i]==1){
                i++;
            }
        }

    }

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

这里要求one pass完成排序，需要利用只有数组元素只有3个数的特性，否则无法完成。排序完成后一定是0...01...12....2，所以可以扫描数组，当遇到0时，交换到前部，当遇到1时，交换到后部。用双指针left, right来记录当前已经就位的0序列和2序列的边界位置。

假设已经完成到如下所示的状态：

0......0 1......1 x1 x2 .... xm 2.....2

          \|           \|               \|

        left        cur          right

(1) A[cur] = 1：已经就位，cur++即可

(2) A[cur] = 0：交换A[cur]和A[left]。由于A[left]=1或left=cur，所以交换以后A[cur]已经就位，cur++，left++

(3) A[cur] = 2：交换A[cur]和A[right]，right--。

由于xm的值未知，cur不能增加，继续判断xm。cur>right扫描结束。