小米笔试 （红白蓝彩条排序）

参考题解1

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

另一种写法：
1. 用三个变量a b c分别记录0 1 2 的个数
2. 先扫描统计三个数分别有多少个，然后再从前往后先写a个0 b个1 c个2

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int count[3] = {0};

        for(int i = 0; i < nums.size(); ++i)
            ++count[nums[i]];

        for(int i = 0, t = 0;i < 3; ++i)
            for(int j = 0; j < count[i]; ++j)
                nums[t++] = i;

    }
};