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; }关键点解析当遇到红色(0)时与left交换并双指针右移遇到蓝色(2)时与right交换且仅right左移因为交换过来的元素可能还是2白色(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 时间复杂度对比方法时间复杂度空间复杂度是否原地计数排序O(n)O(k)否双指针标准O(n)O(1)是单指针两次遍历O(n)O(1)是3.2 常见边界陷阱全0或全2数组需要验证指针不会越界空数组输入应直接返回而不报错超大数组测试确保没有栈溢出风险元素全为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 实际业务场景应用电商价格区间筛选// 将商品按价格分为三档低价(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; } } }日志级别过滤系统// DEBUG(0), INFO(1), ERROR(2) void filterLogs(LogEntry[] logs) { // 相同的双指针逻辑... }5. 算法优化与测试技巧5.1 JMH性能测试对比使用Java Microbenchmark Harness对三种解法进行测试单位ms/op数据规模计数排序双指针单指针两次1,0000.120.080.05100,0001.451.200.981,000,00014.3212.5610.21测试结果显示单指针两次遍历法在实际运行中最快这与CPU缓存命中率有关。5.2 常见面试问题锦集Q为什么遇到2时curr不递增 A因为从右侧交换过来的元素可能还是2需要再次检查Q如何证明算法正确性 A循环不变式证明法left左侧全为0right右侧全为2Q如果要求稳定排序怎么办 A双指针法不稳定需改用其他稳定排序算法6. 从解题到精通的学习路径要真正掌握这类双指针问题建议按照以下路径系统学习基础阶段LeetCode 26. 删除有序数组中的重复项LeetCode 27. 移除元素进阶训练LeetCode 80. 删除有序数组中的重复项 IILeetCode 283. 移动零高阶应用LeetCode 215. 数组中的第K个最大元素快速选择LeetCode 42. 接雨水多指针配合在刷题过程中我习惯用笔记本记录每种题型的解题模板。比如双指针问题通常有以下几个变种同向指针快慢指针相向指针如颜色分类滑动窗口特殊双指针每次遇到新题时先判断属于哪种模式再套用相应的解题框架这样可以大幅提高解题效率。