题目

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.

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?

分析

这题看似简单，但是在单次扫描的条件下，需要注意很多细节。
思路是设置双指针，分别表示red的末尾和blue的开头，从而将整个数组分成三段。

实现

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int N=nums.size();
        int red=0, blue=N-1;
        for(int i=0; i<=blue;){
            if(nums[i]==0)
                swap(nums[i++], nums[red++]);
            else if(nums[i]==2)
                swap(nums[i], nums[blue--]);
            else
                i++;
        }
    }
};

思考

这题据说可以用partition配合bind1st来实现 有空可以了解下。