075 - Sort Colors

Sort Colors

Given an array with n 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 integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note:
You are not suppose to use the library's sort function for this problem.

click to show follow up.

Follow up:
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?

Hide Tags

Array Two Pointers Sort

Hide Similar Problems

(M) Sort List

 

实际上就是0,1,2的 in place 排序。

想法是用三个下标 idx_0, idx_1, idx_2，分别表示0, 1, 2 的边界（也就是第一个不是0, 1, 2的位置），

idx_0 从前往后移动，另外两个从后往前移动，主要是为了能尽快把2送到后面，0，换到前面。

依次交换：

先交换idx_1 和 idx_2 指向的数字，此时 idx_1 指向的可能是 0， 或者 2，

    如果是0不动，是2看两者相对位置来决定是否交换，或者是把idx_1向前移动来跳过这个 2.

    （例如 0，1，2，idx_1 = 2, idx_2 = 1，此时就可以直接让idx_1向前移动跳过最后那个2）

然后根据idx_0指向的值来交换，如果是2，则交换idx_0 跟 idx_2的值，如果是1，则交换 idx_0 和 idx_1的值。

交换完毕之后，刷新各自的idx到新的边界。

循环的终止条件是如果 idx_1 或者 idx_2 遇到或者越过 idx_0，否则一直循环；

但如果 idx_0 和 idx_1 停在同一个地方，且这个地方还是个2，说明 1 的前面还有个2 ，

所以此时也得继续循环。

整个思路比较啰嗦。。。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int sz=nums.size();
        if(sz>1)
        {
            int idx_0=0, idx_1=sz-1, idx_2=sz-1;

            while(((idx_1>idx_0)&&(idx_2>idx_0)) || (idx_0==idx_1 && idx_2 && 2==nums[idx_0]))
            {
                findnext0(nums, idx_0);
                findnext1(nums, idx_1);
                findnext2(nums, idx_2);

                if((2 == nums[idx_1]))
                {
                    if(idx_1<idx_2)
                    {
                        nums[idx_1] = nums[idx_2];  //findnext1(nums, idx_1);
                        nums[idx_2] = 2;            //findnext2(nums, idx_2);
                    }
                    else
                    {
                        idx_1 = idx_2;              //findnext1(nums, idx_1);
                    }
                }
   
                if((2 == nums[idx_0])&&(idx_0<idx_2))
                {
                    nums[idx_0] = nums[idx_2];      //findnext0(nums, idx_0);
                    nums[idx_2] = 2;                //findnext2(nums, idx_2);
                }
               
                if((1 == nums[idx_0])&&(idx_0<idx_1))
                {
                    if(!nums[idx_1])
                    {
                        nums[idx_0] = nums[idx_1];  //findnext0(nums, idx_0);
                        nums[idx_1] = 1;            //findnext1(nums, idx_1);
                    }
                }
            }
        }
    }
   
    void findnext0(vector<int>& nums, int& idx)
    {
        int zz = nums.size();
            while(zz>idx && !nums[idx])
                idx++;
    }
    void findnext1(vector<int>& nums, int& idx)
    {
        int zz = nums.size();
            while(0<idx && 1 == nums[idx])
                idx--;
    }
    void findnext2(vector<int>& nums, int& idx)
    {
        int zz = nums.size();
            while(0<idx && 2 == nums[idx])
                idx--;
    }
};

4 ms.

 

讨论区有个one pass java的，只用了两个下标，过程还是一样的交换，写得挺简练。