leetcode 链接：75. 颜色分类

题目

给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

进阶：

• 你可以不使用代码库中的排序函数来解决这道题吗？
• 你能想出一个仅使用常数空间的一趟扫描算法吗？

示例：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

输入：nums = [2,0,1]
输出：[0,1,2]

输入：nums = [0]
输出：[0]

输入：nums = [1]
输出：[1]

解答 & 代码

解法一：统计个数，两次遍历

• 第一次遍历数组，分别统计 0、1 的个数 redCnt、whiteCnt。
• 第二次遍历数组，将前 redCnt 个数置为 0，将中间的 whiteCnt 个数置为 1，将后面剩余的数置为 2

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

  执行结果： ``` 执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户 内存消耗：8.1 MB, 在所有 C++ 提交中击败了 27.07% 的用户

<a name="DbuvS"></a>
## 解法二：一次遍历
```cpp
class Solution {
public:
    void sortColors(vector<int>& nums) {
        int size = nums.size();
        if(size <= 1)
            return;

        int sep1 = 0;            // 0、1 之间的边界（重排后第一个 1 的位置）
        int sep2 = size - 1;    // 1、2 之间的边界（重排后最后一个 1 的位置）
        int i = 0;                // 当前遍历到的元素下标
        // 遍历，直到走到 1、2 边界（后面的元素已经全为 2，不用再遍历）
        while(i <= sep2)
        {
            if(nums[i] == 0)            // 若当前元素为 0
            {
                swap(nums[i], nums[sep1]);    // 将当前元素和 sep1 的元素交换
                ++sep1;                        // 边界 sep1 右移
                ++i;                        // i 右移
            }
            else if(nums[i] == 1)        // 若当前元素为 1
                ++i;                        // i 右移
            else if(nums[i] == 2)        // 若当前元素为 2
            {
                swap(nums[i], nums[sep2]);    // 将当前元素和 sep2 的元素交换
                --sep2;                        // 边界 sep2 右移
                // 交换后位置 i 是原来 sep2 位置的元素，还未处理过，因此 i 先不右移
            }
        }
    }
};

执行结果：

执行结果：通过

执行用时：4 ms, 在所有 C++ 提交中击败了 46.47% 的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了 82.44% 的用户

改了下变量的含义，更好理解：

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int len = nums.size();
        int cnt0 = 0;    // 当前 0 的个数，也即当前 0 的开区间右边界
        int cnt2 = 0;    // 当前 2 的个数，len - cnt2 - 1 也即当前 2 的开区间左边界
        int idx = 0;    // 当前遍历到的下标
        // 遍历，直到走到 2 的闭区间左边界，停止向前
        while(idx <= len - cnt2 - 1)
        {
            if(nums[idx] == 0)
            {
                swap(nums[idx], nums[cnt0]);
                ++idx;
                ++cnt0;
            }
            else if(nums[idx] == 1)
                ++idx;
            else if(nums[idx] == 2)
            {
                swap(nums[idx], nums[len - cnt2 - 1]);
                ++cnt2;
            }
        }
    }
};

执行结果：

执行结果：通过

执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了 73.58% 的用户