LeetCode 75. 颜色分类
目录
题目描述
✅ 75. 颜色分类
题意分析
输入是一个只含 0、1、2 三种取值的整数数组，要求把它重排成「所有 0 在前、所有 1 居中、所有 2 在后」的样子。题目额外要求原地修改，不允许先复制一份再写回。
「取值只有三种」是一个非常强的约束信号：元素之间的大小关系不需要逐对比较就能知道，看一眼值就知道它最终该落在数组的哪一段。这意味着通用比较排序的 $O(n\log n)$ 是被浪费掉的信息量。
「原地」这个词排除了计数后重新分配一个新数组的写法，额外空间必须是常数级；进阶要求还进一步限制只能扫描一趟，也就是说不能先数一遍再填一遍。
需要留意的边界：数组长度可能只有 1；数组可能本来就有序；数组可能全是同一种颜色（全 0、全 1、全 2）；也可能完全逆序，比如
[2,2,1,1,0,0]。这几种情况都要保证不越界、不死循环。
解法：三指针原地分区
核心思路
问题关键：数组只有 0、1、2 三种值，不需要通用排序，可以直接把元素放进对应区间。
为什么选三路分区：计数法虽是 $O(n)$，但要先统计再覆盖；三路分区能在一次扫描中原地完成，同时满足进阶要求。
区间不变量：用
zero、i、two将数组划成四段：[0, zero)全是 0，[zero, i)全是 1，[i, two]尚未处理，(two, n - 1]全是 2。每轮只检查nums[i]，让未知区至少缩小一格。遇到 0 时与
zero交换，并同时推进zero、i；遇到 1 只推进i；遇到 2 时与two交换并只缩小two。最后一种情况不能推进i，因为从右侧换回来的元素仍属于未知区，必须再次判断。
解题步骤
- 初始化
zero = 0、i = 0、two = n - 1，此时整个数组都是未知区。- 当
i <= two时检查nums[i]。- 值为 0：与
nums[zero]交换，zero++、i++。- 值为 1：位置已经正确，只执行
i++。- 值为 2：与
nums[two]交换，只执行two--，下一轮重新检查nums[i]。例如
[2,0,2,1,1,0]：第一次把开头的 2 与末尾 0 交换后，i不动，下一轮继续处理换回来的 0；最终得到[0,0,1,1,2,2]。
代码实现
class Solution {
public void sortColors(int[] nums) {
int zero = 0;
int i = 0;
int two = nums.length - 1;
while (i <= two) {
if (nums[i] == 0) {
swap(nums, zero, i);
zero++;
i++;
} else if (nums[i] == 2) {
// 从右侧换来的元素还没检查，i 不能前进。
swap(nums, i, two);
two--;
} else {
i++;
}
}
}
private void swap(int[] nums, int i, int j) {
int value = nums[i];
nums[i] = nums[j];
nums[j] = value;
}
}
func sortColors(nums []int) {
zero := 0
i := 0
two := len(nums) - 1
for i <= two {
if nums[i] == 0 {
nums[zero], nums[i] = nums[i], nums[zero]
zero++
i++
} else if nums[i] == 2 {
// 右侧交换回来的值属于未知区，需要继续检查。
nums[i], nums[two] = nums[two], nums[i]
two--
} else {
i++
}
}
}
复杂度分析
- 时间复杂度：$O(n)$。每轮都让未知区
[i, two]缩小一格，每个元素最多被处理一次。- 空间复杂度：$O(1)$。只使用三个指针和交换临时变量。
关键点总结
- 先写出四段区间的不变量，再推导指针移动，比背代码可靠。
- 从已处理区换回的元素可以跳过；从未知区换回的元素必须重新检查。
- 未知区是闭区间
[i, two]，所以循环条件必须是i <= two。- 该方法就是荷兰国旗算法，也是快速排序三路划分的核心过程。
易错点总结
- 处理 2 后仍执行
i++：[2,2,0,1]会漏检从右侧换回的 0，得到[1,0,2,2]。- 循环写成
i < two：i == two时仍有一个未知元素，[1,2,0]会提前结束为[1,0,2]。two初始化为nums.length：第一次交换到右侧就会数组越界，应为最后一个下标nums.length - 1。- 处理 0 后只推进
zero：[0]会重复处理同一位置并最终越界，zero与i都要推进。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 283. 移动零 | 简单 | 只需两段划分而非三段，且要求保持非零元素的相对顺序，因此只能同向双指针覆盖，不能任意交换 |
| 27. 移除元素 | 简单 | 同样是原地分区，但目标值由题目给定且只分「保留」与「丢弃」两段，返回的是新长度而非重排后的完整数组 |
| 26. 删除有序数组中的重复项 | 简单 | 输入已有序，分区依据是「与前一个元素是否相等」而非元素自身取值，判断条件依赖相邻关系 |
| 88. 合并两个有序数组 | 简单 | 双指针从后往前填充而非从两端向中间收缩，核心是避免覆盖未处理数据，与本题的未知区收缩方向相反 |
| 215. 数组中的第K个最大元素 | 中等 | 用的是同一套 partition，但只需递归进入包含目标下标的那一侧，是选择而非完整排序 |
| 324. 摆动排序 II | 中等 | 在三路划分之上还要叠加下标映射，把大小两半交错写入，难点从分区本身转移到穿插位置的推导 |