LC75　颜色分类¶

中等通过率 63.9%python3核心代码模式技巧样例通过牛客 AC数组双指针冒泡排序排序快速排序

牛客原题　源码

讲解章节：双指针与滑动窗口

一句话

值域只有 0/1/2，用三路划分一趟扫描就地排好。

解题思路¶

这题考什么¶

元素只有三种取值，这是全部信息量所在。通用排序按比较做，下界是 O(n log n)，但这里根本不需要比较——只要把数组切成「0 区 | 1 区 | 未知区 | 2 区」四段，边扫边把未知区的第一个元素归到它该去的那一段。

这就是荷兰国旗问题（Dutch national flag，Dijkstra 提出，因荷兰国旗的红白蓝三色横条得名），也是三路快排的划分步骤。维护三个下标，含义就是循环不变量，全程必须成立：

nums[0 : low]      全是 0（已定稿）
nums[low : mid]    全是 1（已定稿）
nums[mid : high+1] 未知，待处理
nums[high+1 : n]   全是 2（已定稿）

每步看 nums[mid]： == 0 -> 与 nums[low] 交换，low 与 mid 同时右移； == 1 -> 已在正确的段里，mid 右移即可； == 2 -> 与 nums[high] 交换，high 左移，mid 不动。未知区每步至少缩短 1，所以循环一定终止，扫描只走一趟。

另一种写法是「计数排序」：数一遍 0/1/2 的个数，再按个数覆写数组。结果同样正确，但要扫两趟，也绕开了本题真正想教的三路划分。排序与划分的系统讲法见排序。

数据规模与复杂度¶

1 <= n <= 300，nums[i] 只可能是 0、1、2。时间 O(n)：mid 与 high 之间的未知区每次迭代至少缩窄一格。额外空间 O(1)，只有三个下标，符合进阶要求的「常数空间、一趟扫描」。 n 只有 300，任何做法都跑得动，本题考的是写法而非速度；题面也明确禁止直接调用库内置的 sort。

坑在哪¶

换到 2 之后 mid 不能前进。high 那一侧的元素还没被检查过，换过来的可能是 0，需要在下一轮重新判定。写成三个分支都 mid += 1， [2, 0, 1] 会输出 [1, 0, 2]——换来的 0 被跳过，再没机会归位。换到 0 时则可以放心 mid += 1：low 位置上原本是已经检查过的 1 （或 low == mid，换的是自己），换过来的一定不需要再看。
循环条件是 mid <= high，等号要带。未知区收缩到只剩一个元素时 mid == high，那个元素仍未定稿；写成 mid < high 会漏掉它， [1, 0] 之类的输入就会出错。
high 指向的是未知区的右端，不是 2 区的左端。初值取 n - 1 而不是 n，交换时用 nums[high]。取成 n 会立刻越界，取成 n - 2 会漏掉末位元素。
签名返回 None，答案留在入参里。判题驱动对 void 题会回头读入参（见 scripts/corerun.py 的 call_function），必须原地改 nums。写 nums = sorted(nums) 只是重新绑定局部名字，调用方看到的还是原数组。
三个分支的判定顺序不影响正确性（三种取值互斥），但 0 与 2 的分支必须各自配对好「动哪个指针」，写串了会破坏循环不变量。
严格比对：排好序的 0/1/2 序列唯一，没有多解。

样例复核¶

nums = [2, 0, 2, 1, 1, 0]，初始 low = mid = 0，high = 5。

mid=0 值 2 -> 与 nums[5] 换，[0,0,2,1,1,2]，high=4，mid 不动
mid=0 值 0 -> 与 nums[0] 换（自己换自己），low=1，mid=1
mid=1 值 0 -> 与 nums[1] 换，low=2，mid=2
mid=2 值 2 -> 与 nums[4] 换，[0,0,1,1,2,2]，high=3，mid 不动
mid=2 值 1 -> 原地，mid=3
mid=3 值 1 -> 原地，mid=4 > high=3，结束

输出 [0, 0, 1, 1, 2, 2]，与题面一致。第一步与第四步正是「换 2 后 mid 不动」的现场：若那时 mid 也前进，换过来的 0 就被永久跳过了。

参考实现¶

solutions/leetcode/LC75/sol.py
from typing import List, Optional


class Solution:
    def sortColors(self, nums: List[int]) -> None:
        # 循环不变量（全程成立）：
        #   nums[0 : low] 全 0，nums[low : mid] 全 1，
        #   nums[mid : high + 1] 未知，nums[high + 1 : n] 全 2。
        # high 是未知区的右端下标，取 n - 1 而不是 n，否则第一次交换就越界
        low, mid, high = 0, 0, len(nums) - 1
        # 等号必须带：未知区剩最后一个元素时 mid == high，它仍未定稿
        while mid <= high:
            if nums[mid] == 0:
                # 0 要进左段。low 处原本是已检查过的 1（或就是 mid 自己），
                # 换过来的不必重看，所以 low 与 mid 可以一起右移
                nums[low], nums[mid] = nums[mid], nums[low]
                low += 1
                mid += 1
            elif nums[mid] == 2:
                # 2 要进右段。high 处的元素**从未被检查过**，换过来的可能是 0，
                # 所以 mid 原地不动，下一轮重新判定这个位置
                nums[mid], nums[high] = nums[high], nums[mid]
                high -= 1
            else:
                # 1 已经落在 [low, mid) 该在的段里，只需把它并入 1 区
                mid += 1

LC75 颜色分类¶