LeetCode 75. 颜色分类

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，结束

官方解法

一、解法 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 一趟扫描」：理解「双边界同步移动」的思路，深入掌握荷兰国旗问题的本质。