0075. Sort Colors¶
题目信息¶
- 题号:
颜色分类
- 难度:
Medium
- 主题:
数组、计数、双指针、原地分区
- 原题:
- 重点:
从统计三种颜色,推导到两次分区,再用荷兰国旗算法单遍原地排序
题目重述¶
给定整数数组 nums,其中每个元素只可能是 0、1 或 2,分别代表红、白、蓝三种颜色。
请直接修改原数组,使所有 0 位于前面,所有 1 位于中间,所有 2 位于后面。
不能调用语言提供的通用排序函数。数组长度满足 1 <= nums.length <= 300。进阶要求是只扫描一次数组,并使用
O(1) 额外空间。
自建示例¶
输入:nums = [1,2,0,1,2,0,0]
修改后:[0,0,0,1,1,2,2]
三个 0 进入左段,两个 1 留在中段,两个 2 进入右段。
输入:nums = [2,0,2,1,1,0]
修改后:[0,0,1,1,2,2]
右端交换回来的元素仍可能未分类,因此处理 2 时不能立刻推进扫描指针。
输入:nums = [1,1,1]
修改后:[1,1,1]
数组可以缺少某些颜色,三个分区仍然成立。
C++ 实现¶
#include <algorithm>
#include <vector>
class Solution {
private:
void countingOverwrite(std::vector<int>& nums) {
int count[3] = {0, 0, 0};
for (int value : nums) {
++count[value];
}
int write = 0;
for (int value = 0; value < 3; ++value) {
for (int copies = 0; copies < count[value]; ++copies) {
nums[write++] = value;
}
}
}
void twoPartitions(std::vector<int>& nums) {
int zero_end = 0;
for (int scan = 0; scan < static_cast<int>(nums.size()); ++scan) {
if (nums[scan] == 0) {
std::swap(nums[zero_end], nums[scan]);
++zero_end;
}
}
int one_end = zero_end;
for (int scan = zero_end; scan < static_cast<int>(nums.size()); ++scan) {
if (nums[scan] == 1) {
std::swap(nums[one_end], nums[scan]);
++one_end;
}
}
}
void dutchFlag(std::vector<int>& nums) {
int low = 0;
int current = 0;
int high = static_cast<int>(nums.size()) - 1;
while (current <= high) {
if (nums[current] == 0) {
std::swap(nums[low], nums[current]);
++low;
++current;
} else if (nums[current] == 1) {
++current;
} else {
std::swap(nums[current], nums[high]);
--high;
}
}
}
public:
void sortColors(std::vector<int>& nums) {
dutchFlag(nums);
}
};
题解¶
计数覆盖¶
值域只有 0、1、2。先统计三种值的数量,再按数量依次写回,就能在线性时间完成排序:
统计:[count0, count1, count2]
写回:count0 个 0,count1 个 1,count2 个 2
计数数组大小固定为 3,因此额外空间仍是 O(1)。该方法需要一次统计和一次写回,没有利用单遍原地分区的结构。
两次分区¶
第一次扫描把所有 0 交换到数组前端。完成后,区间 [0, zero_end) 已全部确定为 0。
第二次只扫描剩余区间,把所有 1 交换到 zero_end 之后。剩余未被选中的元素只能是 2,因此自然位于末尾。
这种方法把三色排序拆成两次二元分区,时间仍为 O(n),但最坏需要扫描数组两遍。
三段分区¶
单遍方法同时维护四个区间:
[0, low) 已确定为 0
[low, current) 已确定为 1
[current, high] 尚未分类
(high, n) 已确定为 2
初始时前三个已分类区间为空,整个数组都是未知区。每轮只检查 nums[current],并按它的值缩小未知区。
当前值为零¶
当 nums[current] == 0 时,它应进入左侧零区,因此与 nums[low] 交换。
若 low < current,nums[low] 来自已经确认的一区,交换到 current 后仍然已经分类;若
low == current,交换等价于不变。因此交换后可以同时增加 low 和 current。
当前值为一¶
当 nums[current] == 1 时,它已经位于中间区域应扩展的位置,不需要交换,只增加 current。
当前值为二¶
当 nums[current] == 2 时,它应进入右侧二区,因此与 nums[high] 交换并减少 high。
交换回来的元素来自未知区,可能是 0、1 或 2,尚未分类。因此此时不能增加 current,下一轮必须继续检查同一位置。
状态跟踪¶
以 [2,0,2,1,1,0] 为例:
数组 |
|
动作 |
|---|---|---|
|
|
当前为 2,与右端交换 |
|
|
当前换入 0,与 |
|
|
当前仍为 0,继续扩大零区 |
|
|
当前为 2,与 |
|
|
两个 1 依次扩大中间区 |
循环不变量¶
每次循环前,零区、一区和二区都只包含对应颜色。三种分支分别把一个未知元素放入正确分区,并保持其他已分类区间不变。
处理 0 或 1 时 current 增加;处理 2 时 high 减少。因此未知区长度
high - current + 1 每轮严格减少。循环结束时 current > high,未知区为空,三个有序分区连接成最终结果。
复杂度¶
计数覆盖、两次分区和荷兰国旗算法的时间复杂度均为 O(n),额外空间均为 O(1)。荷兰国旗算法只需一次分类扫描,
每个元素最多参与常数次检查或交换。