LeetCode 75. 颜色分类

LeetCode 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;
    }
}

复杂度对比

方法	时间复杂度	空间复杂度	特点
计数重排法	O(n)	O(1)	两趟扫描，逻辑直观
三指针法	O(n)	O(1)	一趟扫描，进阶最优解

示例验证

• 示例 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，结束

官方解法

一、解法 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]）

步骤	ptr 初始值	遍历过程	数组变化	ptr 最终值
第一步（找 0）	0	交换 i=1 和 ptr=0 → 交换 i=5 和 ptr=1	[0,0,2,1,1,2]	2
第二步（找 1）	2	交换 i=3 和 ptr=2 → 交换 i=4 和 ptr=3	[0,0,1,1,2,2]	4

二、解法 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 解法对比（核心总结）

解法	遍历次数	核心特点	优点	缺点
两次遍历分阶段排序	2 次	分步归拢 0、1，逻辑极简	易理解、不易出错	多一次遍历，效率略低
p0/p1 一趟扫描	1 次	双边界同步移动，代码紧凑	一趟扫描，无循环嵌套	二次交换逻辑易混淆
p0/p2 一趟扫描	1 次	左右边界夹逼，处理连续 2 鲁棒	最优解、逻辑清晰、鲁棒	需理解 while 处理连续 2 的逻辑

总结

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