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.length1 <= n <= 300nums[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,遇到大量重复元素时比普通快排快得多。
图解
数组(来自本仓库测试数据,下标从 0 开始)
逐帧动画
1 / 4
快捷键:← → 单步,空格播放 / 暂停。
C++17 题解
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 就在正确区域
}
}
}
};
}
单元测试
以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。
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});