Java版LeetCode热题100之颜色分类：深入解析与实战应用

Java版LeetCode热题100之颜色分类：深入解析与实战应用

本文目标：全面、系统地讲解 LeetCode 第75题「颜色分类」（Sort Colors），从题目理解、算法思路、代码实现到面试技巧和实际应用场景，帮助你真正掌握这道经典算法题。

一、原题回顾

题目描述

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数0、1和2分别表示红色、白色和蓝色。

要求：必须在不使用库内置的sort函数的情况下解决这个问题。

示例

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1] 输出：[0,1,2]

约束条件

• n == nums.length
• 1 <= n <= 300
• nums[i]为0、1或2

进阶挑战

你能想出一个仅使用常数空间的一趟扫描算法吗？

二、原题分析

这道题看似简单，但其实蕴含了非常经典的算法思想——荷兰国旗问题（Dutch National Flag Problem），由著名计算机科学家 Edsger W. Dijkstra 提出。

核心难点

• 不能使用排序函数，意味着我们必须自己设计排序逻辑。
• 原地排序，即不能额外申请与输入规模成比例的空间（如新建数组）。
• 一趟扫描 + 常数空间是进阶要求，考验对双指针、交换策略的理解。

问题本质

将一个只包含三种值（0、1、2）的数组，按非降序排列。由于只有三种值，我们可以利用这个特性设计更高效的算法，而不是通用排序（如快排、归并）。

三、答案构思

我们可以从多个角度思考解法：

思路1：计数法（两次遍历）

• 先遍历一次统计 0、1、2 的数量；
• 再遍历一次，按顺序重写数组。

✅ 优点：逻辑清晰，容易实现
❌ 缺点：需要两次遍历，不符合“一趟扫描”的进阶要求

思路2：单指针法（两次遍历）

• 第一次遍历：把所有 0 移到前面；
• 第二次遍历：从上次结束位置开始，把所有 1 移到 0 后面。

✅ 优点：原地操作，空间 O(1)
❌ 缺点：仍需两次遍历

思路3：双指针法（一次遍历）— 方法A

• 使用两个指针p0和p1，分别指向下一个 0 和 1 应该放置的位置；
• 遇到 0 时，先与p0交换，再判断是否需要与p1二次交换（防止 1 被挤出去）；
• 遇到 1 时，直接与p1交换。

✅ 优点：一次遍历，O(1) 空间
⚠️ 注意：逻辑稍复杂，需处理p0 < p1的情况

思路4：双指针法（一次遍历）— 方法B（推荐）

• 使用p0指向 0 的右边界，p2指向 2 的左边界；
• 从左向右遍历，遇到 0 与p0交换，遇到 2 与p2交换；
• 特别注意：交换 2 后不能立即 i++，因为新换来的元素可能是 0 或 2，需再次检查。

✅ 优点：直观、高效、符合“一趟扫描”要求
✅ 是最接近“荷兰国旗”原始解法的实现

四、完整答案（Java实现）

下面提供三种主流解法的完整代码，并附详细注释。

解法一：计数法（两次遍历）

classSolution{publicvoidsortColors(int[]nums){intcount0=0,count1=0,count2=0;// 第一次遍历：统计各颜色数量for(intnum:nums){if(num==0)count0++;elseif(num==1)count1++;elsecount2++;}// 第二次遍历：重写数组intindex=0;while(count0-->0)nums[index++]=0;while(count1-->0)nums[index++]=1;while(count2-->0)nums[index++]=2;}}

✅ 时间复杂度：O(n)，空间复杂度：O(1)
❌ 不满足“一趟扫描”要求

解法二：单指针法（两次遍历）

classSolution{publicvoidsortColors(int[]nums){intn=nums.length;intptr=0;// 指向下一个0应放的位置// 第一次遍历：把所有0移到前面for(inti=0;i<n;i++){if(nums[i]==0){swap(nums,i,ptr++);}}// 第二次遍历：从ptr开始，把所有1移到0后面for(inti=ptr;i<n;i++){if(nums[i]==1){swap(nums,i,ptr++);}}}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}

✅ 原地操作，空间 O(1)
❌ 仍需两次遍历

解法三：双指针法（一次遍历，推荐）

classSolution{publicvoidsortColors(int[]nums){intn=nums.length;intp0=0;// 下一个0应放的位置intp2=n-1;// 下一个2应放的位置inti=0;// 当前遍历位置// 注意：i <= p2，因为p2右边全是2，无需再处理while(i<=p2){if(nums[i]==0){swap(nums,i,p0);p0++;i++;// 换过来的一定是0或1（因为p0 <= i），安全前进}elseif(nums[i]==2){swap(nums,i,p2);p2--;// ⚠️ 关键：i不++！因为从p2换来的可能是0或2，需再次检查}else{// nums[i] == 1，留在中间，直接前进i++;}}}privatevoidswap(int[]nums,inti,intj){inttemp=nums[i];nums[i]=nums[j];nums[j]=temp;}}

✅一次遍历，O(1) 空间，满足进阶要求
✅ 逻辑清晰，是面试官最希望看到的解法

五、代码分析

我们重点分析双指针一次遍历法（解法三）：

核心思想

将数组划分为三个区域：

• [0, p0)：全是 0
• [p0, i)：全是 1
• (p2, n-1]：全是 2
• [i, p2]：待处理区域

随着i向右移动，待处理区域缩小，最终整个数组有序。

关键细节

1. 为什么交换 2 后i不递增？
   因为nums[p2]可能是 0、1 或 2。如果换回来的是 0，我们需要在下一轮把它移到前面；如果是 2，则继续交换。因此必须再次检查当前位置。

2. 为什么交换 0 后i可以递增？
   因为p0 <= i，nums[p0]要么是 1（在中间区域），要么是 0（已处理）。所以换回来的只能是 0 或 1，不会是 2，可以安全前进。

3. 循环终止条件i <= p2
   当i > p2时，说明待处理区域为空，右侧全是 2，排序完成。

六、时间复杂度与空间复杂度分析

详细说明

• 时间复杂度 O(n)：每个元素最多被访问和交换常数次（最多两次交换），整体线性。
• 空间复杂度 O(1)：仅使用几个整型变量，无额外数组或递归栈。
• 一趟扫描：双指针法中i从左到右移动，p2从右向左移动，总共遍历不超过n次。

七、常见问题解答（FAQ）

Q1：为什么不能像快排那样用三路快排？

A：实际上，这道题就是三路快排（Three-way Partitioning）的特例！
三路快排用于处理大量重复元素的情况，将数组分为< pivot、= pivot、> pivot三部分。本题中 pivot=1，0<1，2>1，完全对应。

Q2：如果颜色种类增加到 k 种怎么办？

A：若 k 较小（如 k ≤ 10），仍可用计数法；若 k 很大，则退化为通用排序问题，需用快排、归并等。但本题 k=3 是关键优化点。

Q3：能否用冒泡排序？

A：可以，但时间复杂度 O(n²)，且不符合“高效”要求。面试中应避免。

Q4：为什么双指针法比单指针法更优？

A：虽然时间复杂度相同，但常数因子更小，且满足“一趟扫描”的进阶要求，体现算法设计能力。

八、优化思路

1. 减少交换次数

在双指针法中，可以先判断i != p0再交换，避免不必要的自交换：

if(nums[i]==0&&i!=p0){swap(nums,i,p0);}

但实际影响微乎其微，可读性更重要。

2. 使用位运算交换（不推荐）

nums[i]^=nums[j];nums[j]^=nums[i];nums[i]^=nums[j];

虽然节省一个临时变量，但可读性差、易出错、现代JVM优化后性能无优势，不建议使用。

3. 提前终止

如果发现数组已经有序（如全为1），可提前退出。但最坏情况无改善，且增加判断开销，通常不值得。

九、数据结构与算法基础知识点回顾

1. 双指针技巧

• 同向双指针：如滑动窗口、快慢指针
• 相向双指针：如两数之和、回文判断
• 多区域划分：如本题的三区域划分

2. 原地算法（In-place Algorithm）

• 不使用额外空间（或仅用 O(1) 空间）
• 通过交换、覆盖等方式修改原数组
• 常见于排序、数组重排类问题

3. 荷兰国旗问题

• 经典三色分区问题
• 扩展：任意 pivot 的三路划分
• 应用于三路快排、处理重复元素

4. 稳定性 vs 非稳定性

• 本题不要求稳定性（相同颜色相对顺序可变）
• 若要求稳定，则不能使用交换法，需计数法或归并思想

十、面试官提问环节（模拟）

Q：你能解释一下为什么交换 2 之后不能i++吗？

答：因为从p2位置换过来的元素可能是 0、1 或 2。如果是 0，我们需要在下一轮把它交换到前面；如果是 2，则需要继续与新的p2交换。如果我们直接i++，就会跳过这个元素，导致排序错误。而交换 0 时，由于p0 <= i，换回来的元素只可能是 0 或 1，不会是 2，所以可以安全前进。

Q：如果数组中有负数或大于2的数怎么办？

答：本题约束nums[i] ∈ {0,1,2}，所以无需考虑。但如果扩展，我们可以：

• 先过滤或报错；
• 或修改算法为通用三路划分（以1为pivot）。

Q：这个算法是稳定的吗？

答：不是稳定的。例如[0a, 0b, 2]，交换后可能变成[0b, 0a, 2]，相同元素的相对顺序改变了。如果要求稳定，应使用计数法（按顺序重写）。

Q：能否推广到 k 个颜色？

答：可以，但效率会下降：

• 若 k 小：计数法 O(n + k)
• 若 k 大：需用通用排序 O(n log n)
• 不存在 O(n) 一趟扫描的通用解法（除非 k 为常数）

十一、这道算法题在实际开发中的应用

1. 数据预处理

在机器学习中，常需对标签（label）进行编码和排序。例如将类别标签[2,0,1,0]转换为有序形式，便于后续分组或可视化。

2. 日志分级处理

系统日志按严重程度分为 INFO(0)、WARN(1)、ERROR(2)，需要快速将日志流按级别排序，便于优先处理高危日志。

3. 游戏开发中的状态机

角色状态（IDLE=0, RUN=1, JUMP=2）需要按优先级排序，用于动画播放或AI决策。

4. 网络协议中的包分类

网络包按类型（控制=0, 数据=1, 错误=2）分类，需高效重排以优先处理控制包。

5. 三路快排的实际应用

Java 的Arrays.sort()对基本类型使用双轴快排，对对象使用归并；但在处理大量重复元素时，三路划分能显著提升性能。

十二、相关题目推荐

💡 建议：掌握本题后，尝试解决上述题目，巩固双指针和原地操作思想。

十三、总结与延伸

核心收获

1. 荷兰国旗问题是三路划分的经典模型，掌握其思想可解决一类分区问题。
2. 双指针不仅是技巧，更是思维方式：通过维护多个边界，将数组划分为多个逻辑区域。
3. “一趟扫描 + 常数空间”是高级算法设计的标志，体现对数据流动的精准控制。
4. 细节决定成败：如i是否递增、循环终止条件等，往往是 bug 的根源。

延伸思考

• 如果要求稳定排序，如何修改算法？
• 如果颜色值不是 0/1/2，而是任意整数，但只有三种不同值，如何处理？
• 能否用递归实现荷兰国旗问题？（提示：类似快排）

最终建议

• 面试时优先写出双指针一次遍历解法，展示算法深度；
• 务必解释清楚交换 2 后不递增i的原因，这是面试官考察的重点；
• 联系三路快排，展示知识体系的完整性。

结语：算法之美，在于用最简洁的逻辑解决复杂问题。颜色分类虽小，却蕴含了分区、指针、原地操作等核心思想。掌握它，你就离“算法高手”又近了一步！