75. 颜色分类

75. 颜色分类

中等

提示

给定一个包含红色、白色和蓝色、共n个元素的数组nums，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数0、1和2分别表示红色、白色和蓝色。

必须在不使用库内置的 sort 函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]

示例 2：

输入：nums = [2,0,1] 输出：[0,1,2]

提示：

• n == nums.length
• 1 <= n <= 300
• nums[i]为0、1或2

进阶：

• 你能想出一个仅使用常数空间的一趟扫描算法吗？

📝 核心笔记：颜色分类 (Sort Colors - Overwrite Method)

1. 核心思想 (一句话总结)

“千层饼刷漆法：默认先把当前位置刷成蓝色 (2)；如果发现是白色或红色，就往前回溯刷一层白色 (1)；如果发现是红色，再往更前回溯刷一层红色 (0)。”

• 逻辑：所有的 0 肯定在 1 前面，所有的 1 肯定在 2 前面。
• 操作：

• • 遇到任何数：先填 2。
  • 如果原数是 0 或 1：p1指针处填 1，p1前移。
  • 如果原数是 0：p0指针处填 0，p0前移。

• 关键：p1总是走在p0前面（或重合），覆盖顺序保证了 0 不会覆盖 1，1 不会覆盖 2（在错误的位置）。

2. 算法流程 (Double Pointer)

1. 定义指针：

• • p0：指向下一个该填 0 的位置。
  • p1：指向下一个该填 1 的位置。

1. 遍历 (Loop)：

• • 取出当前值x(必须先取出来，因为nums[i]马上要被修改)。
  • 第一层覆盖：直接nums[i] = 2。
  • 第二层覆盖：如果x <= 1(是 0 或 1)，说明这里本该有 1（或者被 0 挤占的 1），在nums[p1]填 1，p1++。
  • 第三层覆盖：如果x == 0，说明这里本该是 0，在nums[p0]填 0，p0++。

1. 结果：一次遍历完成排序。

🔍 代码回忆清单

// 题目：LC 75. Sort Colors class Solution { public void sortColors(int[] nums) { int p0 = 0; // 0 的右边界 int p1 = 0; // 1 的右边界 for (int i = 0; i < nums.length; i++) { int x = nums[i]; // 1. 必须暂存原值，因为马上要改 // 2. 无论 x 是几，末尾肯定是 2 (贪心策略) nums[i] = 2; // 3. 如果原值是 0 或 1，说明 1 的区域要扩大 // 注意：这里用的是 p1 指针 if (x <= 1) { nums[p1++] = 1; } // 4. 如果原值是 0，说明 0 的区域要扩大 // 注意：这里会覆盖掉刚才可能填入的 1 (如果 p0 < p1)， // 但没关系，因为 p1 已经往前走了，相当于把那个 1 "推"到了后面 if (x == 0) { nums[p0++] = 0; } } } }

⚡ 快速复习 CheckList (易错点)

• [ ]为什么要先int x = nums[i]？

• • 因为下一行nums[i] = 2直接把原数据抹掉了。如果不存，后面判断x <= 1就没依据了。

• [ ]逻辑顺序能反吗？

• • 绝对不能。必须是先填2->判断<=1 填1->判断==0 填0。
  • 就像刷墙一样，必须先刷底漆，再刷面漆。对于 0 来说，它既满足<=1也满足==0，所以它会被填两次：先变成 2，再变成 1，最后变成 0。这是正确的。

• [ ]这个写法和经典的 Swap 写法有什么区别？

• • 经典写法是p0, p2双指针交换。
  • 这个写法是覆盖。
  • 优点：代码极短，逻辑顺畅。
  • 缺点：如果题目不仅是排序，还关联了其他对象（比如对象数组），覆盖法会破坏对象的引用，只能用于纯数字排序。

🖼️ 数字演练

nums = [2, 0, 1]初始p0=0, p1=0.

1. i=0, x=2:

• • nums[0] = 2->[2, 0, 1].
  • x<=1? No.
  • x==0? No.
  • 状态：[2, 0, 1],p0=0, p1=0.

1. i=1, x=0:

• • nums[1] = 2->[2, 2, 1].
  • x<=1? Yes.nums[p1] = nums[0] = 1.p1++-> 1. 数组变[1, 2, 1].
  • x==0? Yes.nums[p0] = nums[0] = 0.p0++-> 1. 数组变[0, 2, 1].
  • 状态：[0, 2, 1],p0=1, p1=1. (注意：位置 0 先被改成 1，立刻又被改成 0，正确).

1. i=2, x=1:

• • nums[2] = 2->[0, 2, 2].
  • x<=1? Yes.nums[p1] = nums[1] = 1.p1++-> 2. 数组变[0, 1, 2].
  • x==0? No.
  • 状态：[0, 1, 2].

最终结果:[0, 1, 2].