1. 问题背景与核心挑战颜色分类Sort Colors是LeetCode题库中的经典题目编号75。题目要求对包含红、白、蓝三种颜色的数组进行原地排序使得相同颜色相邻且按红、白、蓝顺序排列。这个问题看似简单却蕴含着算法设计的精妙之处。在实际开发中类似场景比比皆是。比如电商平台的商品按价格区间分类、日志系统按紧急程度过滤消息甚至游戏开发中按对象类型批量处理实体。理解这个问题的解法能帮助我们掌握处理分类问题的通用思路。题目给出的约束条件非常关键必须使用原地排序算法空间复杂度O(1)只能遍历数组一次时间复杂度O(n)颜色用整数0、1、2表示这些限制排除了简单的计数排序和标准库sort方法迫使我们寻找更巧妙的解决方案。2. 解法一双指针交换法2.1 基本思路双指针法是解决这类问题的黄金标准。我们维护两个指针left指针标记0红色的右边界right指针标记2蓝色的左边界当前指针i用于遍历数组核心思想是通过交换操作将0移到左侧2移到右侧自然1就会留在中间。public void sortColors(int[] nums) { int left 0, right nums.length - 1; int i 0; while (i right) { if (nums[i] 0) { swap(nums, left, i); } else if (nums[i] 2) { swap(nums, right--, i); } else { i; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }2.2 关键点解析边界条件处理当nums[i]2时i不递增是因为交换过来的元素可能还是2循环终止条件i right而非i nums.length指针移动逻辑只有确认当前元素是1时才移动i注意在面试中面试官通常会要求解释为什么nums[i]2时不递增i。这是最容易出错的地方需要重点准备。3. 解法二计数排序变种3.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; } } }3.2 适用场景分析这种方法虽然不满足题目要求但在实际工程中当颜色种类固定且较少时如本例的3种需要稳定排序时允许使用额外空间时是更直观且易维护的选择。面试时可以先提出这种解法再优化为双指针法展示思维过程。4. 算法复杂度对比方法时间复杂度空间复杂度是否原地遍历次数双指针法O(n)O(1)是1计数排序变种O(n)O(k)否2标准库排序O(nlogn)O(logn)视实现多次5. 边界条件与测试用例设计完整的测试应该包含以下场景空数组输入单元素数组全0/全1/全2数组已排序数组逆序数组随机混合数组超大数组性能测试Test public void testSortColors() { // 常规测试 int[] test1 {2,0,2,1,1,0}; sortColors(test1); assertArrayEquals(new int[]{0,0,1,1,2,2}, test1); // 边界测试 int[] test2 {2}; sortColors(test2); assertArrayEquals(new int[]{2}, test2); // 性能测试 int[] largeArray new int[1000000]; // 填充测试数据... }6. 实际工程应用案例6.1 电商价格区间筛选假设我们需要对商品按价格区间快速分类0-100元0100-500元1500元以上2使用双指针法可以在用户滑动筛选条时实时更新商品列表。6.2 日志级别过滤系统日志通常分为ERROR0WARN1INFO2需要快速过滤显示特定级别的日志时同样的算法可以高效处理。7. 常见面试问题与回答策略Q: 为什么nums[i]2时不递增i A: 因为交换过来的元素可能还是2需要再次检查。而交换0时我们可以确定换过来的只能是1因为左边的都已经处理过Q: 如何证明算法的正确性 A: 可以维护循环不变式left左侧全是0right右侧全是2left到i之间全是1Q: 如果颜色增加到5种怎么办 A: 双指针法可以扩展为多指针但更推荐使用计数排序或标准库sortQ: 这个算法是稳定的吗 A: 不是相同颜色的相对顺序可能会改变。如果需要稳定排序应该使用其他方法8. 算法优化与变种8.1 三指针实现对于颜色种类更多的情况可以扩展为三指针// 假设颜色为0,1,2,3 int low 0, mid 0, high nums.length - 1; while (mid high) { if (nums[mid] 0) { swap(nums, low, mid); } else if (nums[mid] 1) { mid; } else if (nums[mid] 2) { swap(nums, mid, high--); } else { // 处理颜色3... } }8.2 并行化处理对于超大数组可以考虑分块并行处理将数组分成k个块每个线程统计自己块内的颜色计数汇总计数后计算每个块的写入位置并行执行写入9. 与其他算法题的关联颜色分类与以下算法题有密切联系移动零LeetCode 283可以看作只有0和非0两种颜色按奇偶排序数组LeetCode 905二进制分类问题荷兰国旗问题完全相同的题目理解这些问题的共性可以建立分类问题的通用解决框架。10. 刷题建议与学习路径对于准备面试的开发者建议先掌握基础的双指针实现理解算法正确性的证明方法练习各种边界条件的测试用例尝试用不同语言实现思考实际工程中的应用场景进阶学习可以关注多指针技巧并行算法优化稳定性与性能的权衡泛型实现如果语言支持这个问题的价值不仅在于解法本身更在于培养分类处理问题的思维方式。在实际工程中类似的需求随处可见掌握这类算法能显著提升代码效率和质量。 
长河君 · 2026/10/31 19:12:45 · 阅读 1.2k 双指针法解决颜色分类问题：LeetCode 75题解析
1. 问题背景与核心挑战颜色分类Sort Colors是LeetCode题库中的经典题目编号75。题目要求对包含红、白、蓝三种颜色的数组进行原地排序使得相同颜色相邻且按红、白、蓝顺序排列。这个问题看似简单却蕴含着算法设计的精妙之处。在实际开发中类似场景比比皆是。比如电商平台的商品按价格区间分类、日志系统按紧急程度过滤消息甚至游戏开发中按对象类型批量处理实体。理解这个问题的解法能帮助我们掌握处理分类问题的通用思路。题目给出的约束条件非常关键必须使用原地排序算法空间复杂度O(1)只能遍历数组一次时间复杂度O(n)颜色用整数0、1、2表示这些限制排除了简单的计数排序和标准库sort方法迫使我们寻找更巧妙的解决方案。2. 解法一双指针交换法2.1 基本思路双指针法是解决这类问题的黄金标准。我们维护两个指针left指针标记0红色的右边界right指针标记2蓝色的左边界当前指针i用于遍历数组核心思想是通过交换操作将0移到左侧2移到右侧自然1就会留在中间。public void sortColors(int[] nums) { int left 0, right nums.length - 1; int i 0; while (i right) { if (nums[i] 0) { swap(nums, left, i); } else if (nums[i] 2) { swap(nums, right--, i); } else { i; } } } private void swap(int[] nums, int i, int j) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; }2.2 关键点解析边界条件处理当nums[i]2时i不递增是因为交换过来的元素可能还是2循环终止条件i right而非i nums.length指针移动逻辑只有确认当前元素是1时才移动i注意在面试中面试官通常会要求解释为什么nums[i]2时不递增i。这是最容易出错的地方需要重点准备。3. 解法二计数排序变种3.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; } } }3.2 适用场景分析这种方法虽然不满足题目要求但在实际工程中当颜色种类固定且较少时如本例的3种需要稳定排序时允许使用额外空间时是更直观且易维护的选择。面试时可以先提出这种解法再优化为双指针法展示思维过程。4. 算法复杂度对比方法时间复杂度空间复杂度是否原地遍历次数双指针法O(n)O(1)是1计数排序变种O(n)O(k)否2标准库排序O(nlogn)O(logn)视实现多次5. 边界条件与测试用例设计完整的测试应该包含以下场景空数组输入单元素数组全0/全1/全2数组已排序数组逆序数组随机混合数组超大数组性能测试Test public void testSortColors() { // 常规测试 int[] test1 {2,0,2,1,1,0}; sortColors(test1); assertArrayEquals(new int[]{0,0,1,1,2,2}, test1); // 边界测试 int[] test2 {2}; sortColors(test2); assertArrayEquals(new int[]{2}, test2); // 性能测试 int[] largeArray new int[1000000]; // 填充测试数据... }6. 实际工程应用案例6.1 电商价格区间筛选假设我们需要对商品按价格区间快速分类0-100元0100-500元1500元以上2使用双指针法可以在用户滑动筛选条时实时更新商品列表。6.2 日志级别过滤系统日志通常分为ERROR0WARN1INFO2需要快速过滤显示特定级别的日志时同样的算法可以高效处理。7. 常见面试问题与回答策略Q: 为什么nums[i]2时不递增i A: 因为交换过来的元素可能还是2需要再次检查。而交换0时我们可以确定换过来的只能是1因为左边的都已经处理过Q: 如何证明算法的正确性 A: 可以维护循环不变式left左侧全是0right右侧全是2left到i之间全是1Q: 如果颜色增加到5种怎么办 A: 双指针法可以扩展为多指针但更推荐使用计数排序或标准库sortQ: 这个算法是稳定的吗 A: 不是相同颜色的相对顺序可能会改变。如果需要稳定排序应该使用其他方法8. 算法优化与变种8.1 三指针实现对于颜色种类更多的情况可以扩展为三指针// 假设颜色为0,1,2,3 int low 0, mid 0, high nums.length - 1; while (mid high) { if (nums[mid] 0) { swap(nums, low, mid); } else if (nums[mid] 1) { mid; } else if (nums[mid] 2) { swap(nums, mid, high--); } else { // 处理颜色3... } }8.2 并行化处理对于超大数组可以考虑分块并行处理将数组分成k个块每个线程统计自己块内的颜色计数汇总计数后计算每个块的写入位置并行执行写入9. 与其他算法题的关联颜色分类与以下算法题有密切联系移动零LeetCode 283可以看作只有0和非0两种颜色按奇偶排序数组LeetCode 905二进制分类问题荷兰国旗问题完全相同的题目理解这些问题的共性可以建立分类问题的通用解决框架。10. 刷题建议与学习路径对于准备面试的开发者建议先掌握基础的双指针实现理解算法正确性的证明方法练习各种边界条件的测试用例尝试用不同语言实现思考实际工程中的应用场景进阶学习可以关注多指针技巧并行算法优化稳定性与性能的权衡泛型实现如果语言支持这个问题的价值不仅在于解法本身更在于培养分类处理问题的思维方式。在实际工程中类似的需求随处可见掌握这类算法能显著提升代码效率和质量。