75. Sort Colors

Given an array with n objects colored red, white or blue, sort them in-place 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.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

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 a one-pass algorithm using only constant space?

---

这道题有意思。实质是要把由0,1,2组成的数组从小到大排序，本来用计数排序，分别统计一下0,1,2这3个数字各有多少个，然后重新构造一个排好序的数组即可，但是Follow up里提到不能使用two-pass算法，并且只能使用常数空间复杂度。 我稍加思考，想到一个可行的算法。因为数组中只有3个数字，那么排好序的数组开头肯定是0（如果有0的话），结尾肯定是2（如果有2的话）。所以我们只需一遍遍历，遇到0则放到开头，遇到2则放到结尾，遇到1的话，就先统计一下1的数目。最后把1重新赋值到所有0的后面，1的个数在前面已经统计过了，所以正好。 完整代码如下：

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int p0 = 0, p2 = nums.size() – 1; // p0和p2分别代表下一个0和2应该填入的位置
        int n1 = 0; // 1的数量
        for (int i = 0; i <= p2; i++) {
            if (nums[i] == 0)
                nums[p0++] = nums[i];
            else if (nums[i] == 1)
                n1++;
            else {
                swap(nums[i], nums[p2]);
                p2–;
                i–;
            }
        }
        for (int i = 0; i < n1; i++)
            nums[p0++] = 1;
    }
};

本代码提交AC，用时3MS。

二刷。看评论区的题解，代码如下，zero和second分别表示可以下一个可以放0或者2的位置。i不断往前扫描，遇到2把它放末尾，遇到0把它放开头，如此不断swap之后，1都被扔到中间了。i最多进行了一次扫描。

class Solution {
public:
    void sortColors(vector<int>& nums)
    {
        int zero = 0, second = nums.size() - 1;
        int i = 0;
        while (i <= second) {
            while (i < second && nums[i] == 2) {
                swap(nums[i], nums[second--]);
            }
            while (i > zero && nums[i] == 0) {
                swap(nums[i], nums[zero++]);
            }
            ++i;
        }
    }
};

本代码提交AC，用时6MS。