LeetCode颜色分类问题：双指针算法解析与应用

1. 项目概述：颜色分类问题与LeetCode实战价值

颜色分类（Sort Colors）是LeetCode题库中第75题，也是面试高频出现的经典算法问题。题目要求对包含红、白、蓝三种颜色的数组进行原地排序，其中红色用0表示，白色用1表示，蓝色用2表示。这道题看似简单，却巧妙考察了以下几个核心能力：

• 双指针技巧的灵活应用：如何在O(n)时间复杂度和O(1)空间复杂度下完成排序
• 边界条件的处理能力：指针移动和元素交换时的临界情况判断
• 算法优化意识：从暴力解法逐步优化到最优解法的思考过程

在实际开发中，类似颜色分类的问题场景比比皆是。比如电商平台的商品按价格区间筛选、日志系统按错误等级过滤等，都需要这种高效的分区排序能力。这也是为什么这道题会被纳入LeetCode热题100，成为Java开发者必须掌握的算法基本功之一。

2. 核心算法解析：双指针的三种实现范式

2.1 计数排序法（新手友好版）

最直观的解法是使用计数排序，这也是很多初学者的第一思路：

public void sortColors(int[] nums) { int[] count = new int[3]; for (int num : nums) count[num]++; int index = 0; for (int i = 0; i < count.length; i++) { while (count[i]-- > 0) { nums[index++] = i; } } }

注意：虽然这种方法时间复杂度是O(n)，但需要额外O(k)空间（k为颜色种类数），不满足题目"原地排序"的要求，仅适合作为理解问题的起点。

2.2 双指针标准解法（面试推荐）

荷兰国旗问题经典解法使用三个指针：

• left：指向最后一个红色元素的下一个位置
• right：指向第一个蓝色元素的前一个位置
• curr：当前遍历指针

public void sortColors(int[] nums) { int left = 0, right = nums.length - 1; int curr = 0; while (curr <= right) { if (nums[curr] == 0) { swap(nums, curr++, left++); } else if (nums[curr] == 2) { swap(nums, curr, right--); // 注意curr不递增 } else { curr++; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; }

关键点解析：

1. 当遇到红色(0)时，与left交换并双指针右移
2. 遇到蓝色(2)时，与right交换且仅right左移（因为交换过来的元素可能还是2）
3. 白色(1)时直接跳过

2.3 单指针两次遍历法（性能优化版）

如果允许两次遍历，可以采用更简洁的实现：

public void sortColors(int[] nums) { int ptr = 0; // 第一次处理所有红色 for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) swap(nums, ptr++, i); } // 第二次处理所有白色 for (int i = ptr; i < nums.length; i++) { if (nums[i] == 1) swap(nums, ptr++, i); } }

这种方法虽然时间复杂度仍是O(n)，但实际运行效率可能更高，适合对性能有极致要求的场景。

3. 算法复杂度与边界条件分析

3.1 时间复杂度对比

3.2 常见边界陷阱

1. 全0或全2数组：需要验证指针不会越界
2. 空数组输入：应直接返回而不报错
3. 超大数组测试：确保没有栈溢出风险
4. 元素全为1：指针移动逻辑是否正确

实测中发现，当输入数组长度超过10^5时，递归解法会出现栈溢出，而迭代解法则能稳定运行。这也是为什么工业级代码更推荐使用双指针的迭代实现。

4. 工程实践中的扩展应用

4.1 多颜色分类问题

当颜色种类扩展到k种时，可以采用快速排序的分区思想：

public void sortKColors(int[] nums, int k) { int low = 0, high = nums.length - 1; for (int color = 0; color < k - 1; color++) { int curr = low; while (curr <= high) { if (nums[curr] == color) { swap(nums, curr++, low++); } else { curr++; } } } }

4.2 实际业务场景应用

1. 电商价格区间筛选：

// 将商品按价格分为三档：低价(0)、中价(1)、高价(2) void sortProducts(Product[] products) { int left = 0, right = products.length - 1; int curr = 0; while (curr <= right) { int priceLevel = getPriceLevel(products[curr]); if (priceLevel == 0) { swap(products, curr++, left++); } else if (priceLevel == 2) { swap(products, curr, right--); } else { curr++; } } }

2. 日志级别过滤系统：

// DEBUG(0), INFO(1), ERROR(2) void filterLogs(LogEntry[] logs) { // 相同的双指针逻辑... }

5. 算法优化与测试技巧

5.1 JMH性能测试对比

使用Java Microbenchmark Harness对三种解法进行测试（单位：ms/op）：

测试结果显示，单指针两次遍历法在实际运行中最快，这与CPU缓存命中率有关。

5.2 常见面试问题锦集

1. Q：为什么遇到2时curr不递增？ A：因为从右侧交换过来的元素可能还是2，需要再次检查

2. Q：如何证明算法正确性？ A：循环不变式证明法：left左侧全为0，right右侧全为2

3. Q：如果要求稳定排序怎么办？ A：双指针法不稳定，需改用其他稳定排序算法

6. 从解题到精通的学习路径

要真正掌握这类双指针问题，建议按照以下路径系统学习：

1. 基础阶段：

   • LeetCode 26. 删除有序数组中的重复项
   • LeetCode 27. 移除元素

2. 进阶训练：

   • LeetCode 80. 删除有序数组中的重复项 II
   • LeetCode 283. 移动零

3. 高阶应用：

   • LeetCode 215. 数组中的第K个最大元素（快速选择）
   • LeetCode 42. 接雨水（多指针配合）

在刷题过程中，我习惯用笔记本记录每种题型的解题模板。比如双指针问题通常有以下几个变种：

• 同向指针（快慢指针）
• 相向指针（如颜色分类）
• 滑动窗口（特殊双指针）

每次遇到新题时，先判断属于哪种模式，再套用相应的解题框架，这样可以大幅提高解题效率。