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.length1 n 300nums[i]为0、1或2进阶你能想出一个仅使用常数空间的一趟扫描算法吗 核心笔记颜色分类 (Sort Colors - Overwrite Method)1. 核心思想 (一句话总结)“千层饼刷漆法默认先把当前位置刷成蓝色 (2)如果发现是白色或红色就往前回溯刷一层白色 (1)如果发现是红色再往更前回溯刷一层红色 (0)。”逻辑所有的 0 肯定在 1 前面所有的 1 肯定在 2 前面。操作遇到任何数先填 2。如果原数是 0 或 1p1指针处填 1p1前移。如果原数是 0p0指针处填 0p0前移。关键p1总是走在p0前面或重合覆盖顺序保证了 0 不会覆盖 11 不会覆盖 2在错误的位置。2. 算法流程 (Double Pointer)定义指针p0指向下一个该填 0 的位置。p1指向下一个该填 1 的位置。遍历 (Loop)取出当前值x(必须先取出来因为nums[i]马上要被修改)。第一层覆盖直接nums[i] 2。第二层覆盖如果x 1(是 0 或 1)说明这里本该有 1或者被 0 挤占的 1在nums[p1]填 1p1。第三层覆盖如果x 0说明这里本该是 0在nums[p0]填 0p0。结果一次遍历完成排序。 代码回忆清单// 题目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]初始p00, p10.i0, x2:nums[0] 2-[2, 0, 1].x1? No.x0? No.状态[2, 0, 1],p00, p10.i1, x0:nums[1] 2-[2, 2, 1].x1? Yes.nums[p1] nums[0] 1.p1- 1. 数组变[1, 2, 1].x0? Yes.nums[p0] nums[0] 0.p0- 1. 数组变[0, 2, 1].状态[0, 2, 1],p01, p11. (注意位置 0 先被改成 1立刻又被改成 0正确).i2, x1:nums[2] 2-[0, 2, 2].x1? Yes.nums[p1] nums[1] 1.p1- 2. 数组变[0, 1, 2].x0? No.状态[0, 1, 2].最终结果:[0, 1, 2]. 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.length1 n 300nums[i]为0、1或2进阶你能想出一个仅使用常数空间的一趟扫描算法吗 核心笔记颜色分类 (Sort Colors - Overwrite Method)1. 核心思想 (一句话总结)“千层饼刷漆法默认先把当前位置刷成蓝色 (2)如果发现是白色或红色就往前回溯刷一层白色 (1)如果发现是红色再往更前回溯刷一层红色 (0)。”逻辑所有的 0 肯定在 1 前面所有的 1 肯定在 2 前面。操作遇到任何数先填 2。如果原数是 0 或 1p1指针处填 1p1前移。如果原数是 0p0指针处填 0p0前移。关键p1总是走在p0前面或重合覆盖顺序保证了 0 不会覆盖 11 不会覆盖 2在错误的位置。2. 算法流程 (Double Pointer)定义指针p0指向下一个该填 0 的位置。p1指向下一个该填 1 的位置。遍历 (Loop)取出当前值x(必须先取出来因为nums[i]马上要被修改)。第一层覆盖直接nums[i] 2。第二层覆盖如果x 1(是 0 或 1)说明这里本该有 1或者被 0 挤占的 1在nums[p1]填 1p1。第三层覆盖如果x 0说明这里本该是 0在nums[p0]填 0p0。结果一次遍历完成排序。 代码回忆清单// 题目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]初始p00, p10.i0, x2:nums[0] 2-[2, 0, 1].x1? No.x0? No.状态[2, 0, 1],p00, p10.i1, x0:nums[1] 2-[2, 2, 1].x1? Yes.nums[p1] nums[0] 1.p1- 1. 数组变[1, 2, 1].x0? Yes.nums[p0] nums[0] 0.p0- 1. 数组变[0, 2, 1].状态[0, 2, 1],p01, p11. (注意位置 0 先被改成 1立刻又被改成 0正确).i2, x1:nums[2] 2-[0, 2, 2].x1? Yes.nums[p1] nums[1] 1.p1- 2. 数组变[0, 1, 2].x0? No.状态[0, 1, 2].最终结果:[0, 1, 2].