LeetCode 75. 颜色分类
题目描述
✅ 75. 颜色分类
题意分析
数组只包含
0、1、2三种值，要求原地排列成所有0在前、1居中、2在后的顺序。不能调用库排序，进阶要求只扫描一遍并使用常数额外空间。由于取值只有三种，不需要比较任意两个数来确定大小关系。可以直接把
0送到左端、把2送到右端，让1留在中间；关键是区分哪些位置已经分类，哪些位置仍需检查，避免交换后漏掉未知元素。
解法：三指针原地分区
核心思路
[!blue]
用
zero指向下一个应放0的位置，用two指向下一个应放2的位置，用i检查当前未知元素。始终维护四段：[0, zero)全是0，[zero, i)全是1，[i, two]尚未分类，(two, n)全是2。初始三个已分类区都为空，整个数组属于未知区。遇到
0，把它与nums[zero]交换，再同时增加zero和i。如果zero < i，换回来的值来自已经确定的1区，不需要再检查；如果zero == i，只是原地交换。两种情况下，新增的0都被纳入左区，未知区从左侧缩小一格。遇到
1，它正好可以成为中间区域的新元素，只增加i即可。遇到2，则与nums[two]交换并减小two，把这个2纳入右区。但右端原本也是未知区，换回来的值可能属于任意一类，所以i不能前进，下一轮必须继续检查它。每轮不是推进
i，就是缩小two，未知区都会减少一个位置。即使i == two，仍有一个未知元素需要处理，因此循环条件是i <= two。两者交错时未知区为空，剩下的三段自然按0、1、2排好，交换也始终保留了全部元素。
解题步骤
- 初始化
zero = 0、i = 0、two = n - 1。- 当
i <= two时，检查nums[i]。- 若为
0，与nums[zero]交换，然后同时推进zero、i。- 若为
2，与nums[two]交换，只让two减一，保留i继续检查换入值。- 否则当前值为
1，只让i加一；未知区为空后结束。
代码实现
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)$，未知区初始有
n个位置，每轮恰好缩小一个位置，交换与判断都是常数操作。- 空间复杂度：$O(1)$，只使用三个指针和交换临时变量。
关键点总结
[!green]
- 先写出四段区间的不变量，再推导指针移动，比背代码可靠。
- 从已处理区换回的元素可以跳过；从未知区换回的元素必须重新检查。
- 未知区是闭区间
[i, two]，所以循环条件必须是i <= two。- 该方法就是荷兰国旗算法，也是快速排序三路划分的核心过程。
易错点总结
[!yellow]
- 处理
2后推进i：会跳过从未知右端换回的元素，它可能仍需移到左侧或右侧。- 循环写成
i < two：两者相等时还有一个未知元素，不能提前结束。two初始化为数组长度：它表示可写入2的实际下标，应初始化为n - 1。- 处理
0时只移动一个指针：这个0已经归位，换回的值也已知，因此zero和i都要前进，才能维持四段范围。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 324. 摆动排序 II | 中等 | 同样可以利用三路划分隔开小于、等于、大于枢轴的元素，原题还需虚拟下标控制摆动位置。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！