颜色分类

题面

给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地 对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

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

示例 2：

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

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i] 为 0、1 或 2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

分析

• 可以使用快速排序等算法，时间复杂度为 $O(n\log n )$

• 或者可以利用计数排序，第一遍记录 0、1、2 的出现次数，第二遍覆盖数组

• 代码实现

  class Solution {
  public:
      void sortColors(vector<int>& nums) {
          int c0 = 0, c1 = 0, c2 = 0;
          for (int n : nums) {
              c0 += (n == 0);
              c1 += (n == 1);
              c2 += (n == 2);
          }
          int i = 0;
          while (c0--)
              nums[i++] = 0;
          while (c1--)
              nums[i++] = 1;
          while (c2--)
              nums[i++] = 2;
      }
  };

• 如何使用一边扫描实现？可以维护两个指针，一个指针指向 0 序列的末尾，一个指针指向 1 序列的末尾，而数组的最后一定是 2，因此每次遍历数组时，遇到 0 或 1 就将其填充到前面，否则赋值为 2

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