HHot 100C++ 图解

75. 颜色分类

一句话套路荷兰国旗三向切分;遇 2 交换后 i 不动

题目描述

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

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

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

 

示例 1:

输入:nums = [2,0,2,1,1,0]

输出:[0,0,1,1,2,2]

解释:

该数组包含两个 0、两个 1 和两个 2。将它们原地排序后,所有 0 排在最前面,接着是所有 1,最后是所有 2。

示例 2:

输入:nums = [2,0,1]

输出:[0,1,2]

解释:

数组中有且仅有一个 0、一个 1 和一个 2,按 0、1、2 的顺序原地排列。

 

提示:

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

 

进阶:

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

思路

时间O(n) 一趟
空间O(1)

思路

荷兰国旗三向切分。不变式:[0, p0) 全 0 | [p0, i) 全 1 | [p2+1, n) 全 2 | [i, p2] 待处理i 扫到 0 -> 与 p0 交换并同时前进(换回来的必然是 1 或已处理的 0);

i 扫到 2 -> 与 p2 交换但 i 不动(换回来的值还没看过!这是唯一的坑)。

对比

两趟计数排序(数出 0/1/2 的个数再回填)也能过,但不满足「一趟」的要求;

这就是三路快排的 partition,遇到大量重复元素时比普通快排快得多。

图解

1 0 2 1 0 2 1 3 2 4 0 5 1 6
数组(来自本仓库测试数据,下标从 0 开始)

逐帧动画

1 / 4

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/17_tricks.cpp17 行
namespace lc0075 {
class Solution {
 public:
  void sortColors(vector<int>& nums) {
    int p0 = 0, i = 0, p2 = (int)nums.size() - 1;
    while (i <= p2) {
      if (nums[i] == 0) {
        swap(nums[i++], nums[p0++]);  // 换回的是 1(或自己),可以放心前进
      } else if (nums[i] == 2) {
        swap(nums[i], nums[p2--]);    // 换回来的还没看过,i 不动,下一轮再看
      } else {
        ++i;  // 1 就在正确区域
      }
    }
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q75_sort_colors19 行
lc0075::Solution s;
vector<int> a{2, 0, 2, 1, 1, 0};
s.sortColors(a);
CHECK_EQ(a, vector<int>{0, 0, 1, 1, 2, 2});
vector<int> b{2, 0, 1};
s.sortColors(b);
CHECK_EQ(b, vector<int>{0, 1, 2});
vector<int> c{0};
s.sortColors(c);
CHECK_EQ(c, vector<int>{0});
vector<int> d{2, 2, 2};
s.sortColors(d);
CHECK_EQ(d, vector<int>{2, 2, 2});
vector<int> e{1, 2, 0, 1, 2, 0, 1};
s.sortColors(e);
CHECK_EQ(e, vector<int>{0, 0, 1, 1, 1, 2, 2});
vector<int> f{2, 1, 1, 0};
s.sortColors(f);
CHECK_EQ(f, vector<int>{0, 1, 1, 2});

↑↓ 选择↵ 打开/ 随时唤起