75. 颜色分类#
大家好！今天我们要探讨一个既直观又充满挑战的问题——颜色分类（Color Sort）。这个问题虽然表面上看起来简单，但它背后隐藏着重要的算法思想，在数组处理、原地算法和荷兰国旗问题中都有特殊地位。让我们一起深入这个问题的本质，探索多种巧妙解法！
🌟 颜色分类：把混乱变成秩序#
什么是”颜色分类”？想象你有一堆红白蓝三种颜色的球，现在需要将它们按照红、白、蓝的顺序排列整齐。这个过程就像是整理一面混乱的国旗，让它恢复应有的秩序与美观。
问题描述#
题目目标#
给定一个包含红色、白色和蓝色共 n 个元素的数组 nums ，请你原地对它们进行排序，使相同颜色的元素相邻，并按照红、白、蓝的顺序排列。我们使用整数 0、1 和 2 分别表示红色、白色和蓝色。
示例 1#
输入： nums = [2,0,2,1,1,0]
输出： [0,0,1,1,2,2]
说明： 把输入和输出放在一起看，会更容易直接抓住题目要求的变化。
🎯 问题描述：整理三色数组#
给定一个包含红色、白色和蓝色的数组，把它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色的顺序排列。
这里，我们使用整数0、1和2分别表示红色、白色和蓝色。
注意：不能使用标准库的排序函数来解决这个问题，必须仅使用常数空间的一趟扫描算法。
例如：
输入: [2,0,2,1,1,0]
输出: [0,0,1,1,2,2]🚶♀️ 解法一：计数排序（简单但并非最优）#
最直接的方法是统计数组中0、1、2的个数，然后重新填充数组：
class Solution {
public void sortColors(int[] nums) {
// count0 / count1 / count2 分别记录颜色 0、1、2 的数量
int count0 = 0, count1 = 0, count2 = 0;
// 第 1 次遍历：统计每种颜色出现次数
for (int num : nums) {
// 遇到颜色 0，计数加一
if (num == 0) count0++;
// 遇到颜色 1，计数加一
else if (num == 1) count1++;
// 遇到颜色 2，计数加一
else if (num == 2) count2++;
}
// 第 2 次遍历（写回阶段）：按 0 -> 1 -> 2 的顺序覆盖原数组
// i 是当前写入位置指针
int i = 0;
// 先连续写入 count0 个 0
while (count0 > 0) {
// 写入一个 0 后，写入指针后移
nums[i++] = 0;
// 剩余待写 0 的数量减一
count0--;
}
// 再连续写入 count1 个 1
while (count1 > 0) {
// 写入一个 1 后，写入指针后移
nums[i++] = 1;
// 剩余待写 1 的数量减一
count1--;
}
// 最后连续写入 count2 个 2
while (count2 > 0) {
// 写入一个 2 后，写入指针后移
nums[i++] = 2;
// 剩余待写 2 的数量减一
count2--;
}
}
}时间复杂度：O(n)，需要遍历数组两次
空间复杂度：O(1)，只使用了常数级别的额外空间
这个解法符合题目要求的常数空间，但它需要两次遍历。我们能做得更好吗？
🏇 解法二：双指针法（更优但不是最佳）#
我们可以使用两个指针，分别跟踪应该放置0和1的位置：
class Solution {
public void sortColors(int[] nums) {
int p0 = 0; // 下一个0应该放置的位置
int p1 = 0; // 下一个1应该放置的位置
// i 从左到右扫描数组
for (int i = 0; i < nums.length; i++) {
// 当前元素是 0：需要放到 0 区域尾部
if (nums[i] == 0) {
// 交换当前元素与p0位置的元素
int temp = nums[i];
nums[i] = nums[p0];
nums[p0] = temp;
// 如果p0小于p1，说明我们把一个1换到了当前位置
// 需要再次交换，将1放到正确的位置
if (p0 < p1) {
// 这里复用 temp，把当前位置的 1 交换到 p1 位置
temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
}
// 0 区域和 1 区域边界都向右扩展
p0++;
p1++;
// 当前元素是 1：放到 1 区域尾部
} else if (nums[i] == 1) {
// 交换当前元素与p1位置的元素
int temp = nums[i];
nums[i] = nums[p1];
nums[p1] = temp;
// 1 区域边界右移
p1++;
}
// 当前元素是 2：不处理，留在后侧区域，继续扫描
}
}
}时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(1)，只使用了常数额外空间
这个解法虽然只需要一次遍历，但代码相对复杂，不够直观。
🏆 解法三：荷兰国旗问题（最优解）#
这个问题实际上是由计算机科学家Edsger W. Dijkstra提出的”荷兰国旗问题”的一个变种。荷兰国旗恰好是由红、白、蓝三色组成的，与我们的问题一致。
解法的核心思想是使用三个指针将数组分成四个区域：
- [0, p0)：全部是0（红色）
- [p0, p1)：全部是1（白色）
- [p1, p2]：待分类区域
- (p2, n-1]：全部是2（蓝色）
class Solution {
public void sortColors(int[] nums) {
int p0 = 0; // 指向下一个应放0的位置
int p2 = nums.length - 1; // 指向下一个应放2的位置
int curr = 0; // 当前处理的元素
// 当 curr 超过 p2 时，说明待分类区间为空，排序完成
while (curr <= p2) {
// 情况 1：当前值为 0，应放到最左侧 0 区
if (nums[curr] == 0) {
// 遇到0，与p0位置交换，并移动p0和curr
swap(nums, curr, p0);
// 0 区域扩大一位
p0++;
// curr 位置已经处理完成，移动到下一位
curr++;
// 情况 2：当前值为 2，应放到最右侧 2 区
} else if (nums[curr] == 2) {
// 遇到2，与p2位置交换，并移动p2
// 注意此时curr不移动，因为交换来的元素还未处理
swap(nums, curr, p2);
// 2 区域向左扩展
p2--;
} else {
// 遇到1，只移动curr
// 1 本来就在中间区间，保持不动即可
curr++;
}
}
}
private void swap(int[] nums, int i, int j) {
// 临时变量保存 nums[i]，避免覆盖
int temp = nums[i];
// 把 nums[j] 放到 i 位置
nums[i] = nums[j];
// 把原 nums[i]（temp）放到 j 位置
nums[j] = temp;
}
}时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(1)，只使用了常数额外空间
🎭 荷兰国旗算法的直观理解：拔河游戏#
想象这样一个场景：有三队人（0队、1队、2队）在玩拔河游戏。0队站在左边，2队站在右边，1队站在中间。游戏开始时，大家都混在一起，现在我们要把他们分开。
我们从左向右检查每个人：
- 如果是0队的，就把他与左边区域的边界交换，然后左边区域向右扩展一步
- 如果是2队的，就把他与右边区域的边界交换，然后右边区域向左扩展一步
- 如果是1队的，就保持原位，继续检查下一个人
最终，0队都在最左边，2队都在最右边，1队自然就在中间了。
🎬 图解荷兰国旗算法#
以输入数组 [2,0,2,1,1,0] 为例：
-
初始状态：p0 = 0, curr = 0, p2 = 5 [2,0,2,1,1,0] ^ ^ p0 p2 curr
-
nums[curr] = 2，交换nums[curr]和nums[p2]，p2— [0,0,2,1,1,2] ^ ^ p0 p2 curr
-
nums[curr] = 0，交换nums[curr]和nums[p0]，p0++，curr++ [0,0,2,1,1,2] ^ ^ p0 p2 curr
-
nums[curr] = 2，交换nums[curr]和nums[p2]，p2— [0,0,1,1,2,2] ^ ^ p0 p2 curr
-
nums[curr] = 1，curr++ [0,0,1,1,2,2] ^ ^ p0 p2 curr
-
nums[curr] = 1，curr++ [0,0,1,1,2,2] ^ ^ p0 p2 curr
最终结果为 [0,0,1,1,2,2]，完成排序！
🔍 为什么荷兰国旗算法有效？#
荷兰国旗算法的关键在于维护三个指针，分别表示三个颜色的边界。通过不断调整这些边界，我们可以确保：
- 所有0都被移到数组左侧
- 所有2都被移到数组右侧
- 所有1自然就在中间
这个算法只需要一次遍历，而且空间复杂度是O(1)，达到了时间和空间的双重最优。
🌱 扩展思考：如果有更多种颜色？#
如果有k种颜色（而不仅仅是3种），我们可能需要回到计数排序的思路，或者使用快速排序的partition思想进行多次划分。
class Solution {
public void sortColors(int[] nums, int k) {
// counts[color] 表示颜色 color 出现的次数，颜色范围为 0..k-1
int[] counts = new int[k];
// 统计每种颜色的数量
for (int num : nums) {
// 颜色 num 的计数加一
counts[num]++;
}
// 按颜色从小到大回填数组
// index 表示当前写入 nums 的位置
int index = 0;
// color 从 0 到 k-1 依次处理
for (int color = 0; color < k; color++) {
// 将当前颜色写入 counts[color] 次
for (int count = 0; count < counts[color]; count++) {
// 写入一个 color，并把写入位置后移
nums[index++] = color;
}
}
}
}🌐 实际应用：从排序到分区#
颜色分类问题的思想在现实中有广泛应用：
- 数据处理：将数据分成若干类别进行处理
- 图像处理：图像分割和颜色量化
- 内存管理：垃圾收集算法中的对象分类
- 数据库索引：数据分区提高查询效率
💯 解题心得：特殊问题的特殊解法#
颜色分类问题展示了一个重要的算法设计思想：针对特定问题的特殊性质设计最优算法。
- 当我们知道数据只有少量几种取值时，可以设计比通用排序更高效的解法
- 有时候，问题可以转化为经典问题（如荷兰国旗问题），利用已有的算法思想
- 指针技巧在数组处理中非常有用，特别是需要原地修改数组时
🎓 面试小贴士#
面试中遇到颜色分类问题，建议按以下步骤回答：
- 先提出计数排序的方法，说明这是最直观的两遍扫描法
- 然后介绍双指针的方法，表明你在优化第一个解法
- 最后讲解荷兰国旗算法，展示你对经典算法问题的理解
- 讨论如何将这个思想应用到其他问题，如快速排序中的三路划分
🤔 思考题#
如果数组中有四种颜色（用0,1,2,3表示），如何使用类似荷兰国旗的算法，在一次遍历中完成排序？
颜色分类问题虽然简单，但它是理解分区算法和多指针技巧的绝佳例子。通过这个问题，我们不仅学会了解决特定问题的技巧，还触及了算法设计的一般思路。希望这次探讨能帮助你在数组处理和排序算法方面有更深的理解！
💪 练习建议#
想要巩固对这个问题的理解，不妨尝试：
- 手动模拟荷兰国旗算法的过程，理解三个指针的移动规律
- 尝试实现处理四种颜色的分类算法
- 将这种思想应用到快速排序中，实现三路快排
记住，算法的精髓不在于记忆代码，而在于理解思想。当你能够自然地推导出荷兰国旗算法，你就真正掌握了这个问题背后的核心思想！