LeetCode 热题 100 之 75.颜色分类

方法一：计数重排法（直观易理解）

核心思路：先统计数组中 0、1、2 各自的出现次数，再按顺序将 0、1、2 依次填充回数组。

Java 代码实现：

class Solution { public void sortColors(int[] nums) { int count0 = 0, count1 = 0, count2 = 0; // 1. 统计各颜色数量 for (int num : nums) { if (num == 0) count0++; else if (num == 1) count1++; else count2++; } // 2. 按顺序填充数组 int i = 0; while (count0-- > 0) nums[i++] = 0; while (count1-- > 0) nums[i++] = 1; while (count2-- > 0) nums[i++] = 2; } } 

方法二：三指针法（荷兰国旗问题，一趟扫描，O (1) 空间）

核心思想：用三个指针 p0、p1、p2 划分区间：

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

遍历数组时，根据 nums[p1] 的值进行交换，逐步收缩待处理区间。

Java 代码实现：

class Solution { public void sortColors(int[] nums) { int p0 = 0, p1 = 0, p2 = nums.length - 1; while (p1 <= p2) { if (nums[p1] == 0) { // 遇到 0，交换到 p0 位置，p0 和 p1 都右移 swap(nums, p0, p1); p0++; p1++; } else if (nums[p1] == 1) { // 遇到 1，直接右移 p1 p1++; } else { // 遇到 2，交换到 p2 位置，p2 左移 swap(nums, p1, p2); p2--; } } } private void swap(int[] nums, int i, int j) { int temp = nums[i]; nums[i] = nums[j]; nums[j] = temp; } } 

复杂度对比

示例验证

• 示例 1：nums = [2,0,2,1,1,0]
  • 计数法：count0=2, count1=2, count2=2 → 填充后 [0,0,1,1,2,2] 
  • 三指针法：通过交换逐步将 0 移到左侧，2 移到右侧，最终结果一致 
• 示例 2：nums = [2,0,1]
  • 三指针法：
    • p1=0, nums [p1]=2 → 与 p2 交换 → [1,0,2], p2=1
    • p1=0, nums [p1]=1 → p1 右移 → p1=1
    • p1=1, nums [p1]=0 → 与 p0 交换 → [0,1,2], p0=1, p1=2
    • p1 > p2，结束 

官方解法

力扣官方的三个Java 版本「颜色分类」解法，我会帮你拆解每个解法的核心逻辑、执行细节，以及它们的优缺点和适用场景，让你能清晰区分并灵活运用。

一、解法 1：两次遍历分阶段排序（最易理解）

核心逻辑

把问题拆分为两步，先归拢所有 0，再归拢所有 1，剩下的自然是 2，属于「分步解决」的经典思路。

class Solution { public void sortColors(int[] nums) { int n = nums.length; int ptr = 0; // 标记当前要放置0/1的位置 // 第一步：把所有0交换到数组左侧 for (int i = 0; i < n; ++i) { if (nums[i] == 0) { // 交换nums[i]和nums[ptr]，ptr右移（0的右边界+1） int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } // 第二步：从0的右边界开始，把所有1交换到0的右侧 for (int i = ptr; i < n; ++i) { if (nums[i] == 1) { int temp = nums[i]; nums[i] = nums[ptr]; nums[ptr] = temp; ++ptr; } } } } 

关键细节

• ptr 是「已排序区域的右边界」：第一步结束后，ptr 左侧全是 0；第二步结束后，ptr 左侧全是 0 和 1。
• 无需处理 2：因为 0 和 1 归拢后，剩余位置必然是 2，这是简化问题的核心。

示例推演（nums = [2,0,2,1,1,0]）

二、解法 2：p0/p1 双指针一趟扫描（紧凑版）

核心逻辑

用两个指针同步标记 0 和 1 的右边界，一趟扫描完成排序，核心是「处理 0 时可能需要二次交换 1」。

class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p1 = 0; // p0:0的右边界，p1:1的右边界 for (int i = 0; i < n; ++i) { if (nums[i] == 1) { // 遇到1，直接交换到p1位置，p1右移 int temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; ++p1; } else if (nums[i] == 0) { // 遇到0，先交换到p0位置 int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; // 关键：若p0 < p1，说明p0位置原本是1，被交换到i位置了，需把1换去p1 if (p0 < p1) { temp = nums[i]; nums[i] = nums[p1]; nums[p1] = temp; } // 0和1的边界都右移 ++p0; ++p1; } // 遇到2，直接跳过 } } } 

为什么需要二次交换？

举个反例：nums = [1,0]

• 初始：p0=0，p1=0，i=0 → nums [i]=1 → 交换后 p1=1，数组还是 [1,0]；
• i=1 → nums [i]=0 → 先交换 nums [1] 和 nums [0] → 数组变为 [0,1]；
• 此时 p0=0 <p1=1，但交换 nums [1] 和 nums [1] 无变化，最终结果正确。
• 若没有二次交换，当 p0 <p1 时，交换 0 会把 1 “挤到” i 位置，导致 1 的边界混乱。

三、解法 3：p0/p2 双指针一趟扫描（最优鲁棒版）

核心逻辑

用 p0 标记 0 的右边界、p2 标记 2 的左边界，遍历中把 2 “推到” 右侧，把 0 “拉到” 左侧，1 自然留在中间，是面试最推荐的写法。

class Solution { public void sortColors(int[] nums) { int n = nums.length; int p0 = 0, p2 = n - 1; // p0:0右边界，p2:2左边界 for (int i = 0; i <= p2; ++i) { // 循环处理连续的2：确保i位置不是2（交换后可能还是2） while (i <= p2 && nums[i] == 2) { int temp = nums[i]; nums[i] = nums[p2]; nums[p2] = temp; --p2; // 2的左边界左移 } // 处理0：交换到p0位置，p0右移 if (nums[i] == 0) { int temp = nums[i]; nums[i] = nums[p0]; nums[p0] = temp; ++p0; } } } } 

关键细节

• 用while处理 2：比如nums = [2,2,0]，i=0 时交换后 nums [i] 还是 2，需要继续交换直到 nums [i]≠2；
• 遍历终止条件是i <= p2：因为 p2 右侧已经全是 2，无需处理。

四、三个 Java 解法对比（核心总结）

总结

1. 新手入门选「两次遍历」：拆分问题后几乎无理解成本，适合快速写出可运行代码；
2. 面试最优选「p0/p2 一趟扫描」：一趟扫描 + 常数空间，鲁棒性强，是工业级代码的首选；
3. 进阶学习选「p0/p1 一趟扫描」：理解「双边界同步移动」的思路，深入掌握荷兰国旗问题的本质。