0075. Sort Colors ================= 题目信息 -------- :题号: 0075. 颜色分类 :难度: Medium :主题: 数组、计数、双指针、原地分区 :原题: `LeetCode 0075 `_ :重点: 从统计三种颜色,推导到两次分区,再用荷兰国旗算法单遍原地排序 题目重述 -------- 给定整数数组 ``nums``,其中每个元素只可能是 ``0``、``1`` 或 ``2``,分别代表红、白、蓝三种颜色。 请直接修改原数组,使所有 ``0`` 位于前面,所有 ``1`` 位于中间,所有 ``2`` 位于后面。 不能调用语言提供的通用排序函数。数组长度满足 ``1 <= nums.length <= 300``。进阶要求是只扫描一次数组,并使用 ``O(1)`` 额外空间。 自建示例 -------- .. code-block:: text 输入:nums = [1,2,0,1,2,0,0] 修改后:[0,0,0,1,1,2,2] 三个 ``0`` 进入左段,两个 ``1`` 留在中段,两个 ``2`` 进入右段。 .. code-block:: text 输入:nums = [2,0,2,1,1,0] 修改后:[0,0,1,1,2,2] 右端交换回来的元素仍可能未分类,因此处理 ``2`` 时不能立刻推进扫描指针。 .. code-block:: text 输入:nums = [1,1,1] 修改后:[1,1,1] 数组可以缺少某些颜色,三个分区仍然成立。 C++ 实现 -------- .. code-block:: cpp #include #include class Solution { private: void countingOverwrite(std::vector& nums) { int count[3] = {0, 0, 0}; for (int value : nums) { ++count[value]; } int write = 0; for (int value = 0; value < 3; ++value) { for (int copies = 0; copies < count[value]; ++copies) { nums[write++] = value; } } } void twoPartitions(std::vector& nums) { int zero_end = 0; for (int scan = 0; scan < static_cast(nums.size()); ++scan) { if (nums[scan] == 0) { std::swap(nums[zero_end], nums[scan]); ++zero_end; } } int one_end = zero_end; for (int scan = zero_end; scan < static_cast(nums.size()); ++scan) { if (nums[scan] == 1) { std::swap(nums[one_end], nums[scan]); ++one_end; } } } void dutchFlag(std::vector& nums) { int low = 0; int current = 0; int high = static_cast(nums.size()) - 1; while (current <= high) { if (nums[current] == 0) { std::swap(nums[low], nums[current]); ++low; ++current; } else if (nums[current] == 1) { ++current; } else { std::swap(nums[current], nums[high]); --high; } } } public: void sortColors(std::vector& nums) { dutchFlag(nums); } }; 题解 ---- 计数覆盖 ~~~~~~~~ 值域只有 ``0``、``1``、``2``。先统计三种值的数量,再按数量依次写回,就能在线性时间完成排序: .. code-block:: text 统计:[count0, count1, count2] 写回:count0 个 0,count1 个 1,count2 个 2 计数数组大小固定为 3,因此额外空间仍是 ``O(1)``。该方法需要一次统计和一次写回,没有利用单遍原地分区的结构。 两次分区 ~~~~~~~~ 第一次扫描把所有 ``0`` 交换到数组前端。完成后,区间 ``[0, zero_end)`` 已全部确定为 ``0``。 第二次只扫描剩余区间,把所有 ``1`` 交换到 ``zero_end`` 之后。剩余未被选中的元素只能是 ``2``,因此自然位于末尾。 这种方法把三色排序拆成两次二元分区,时间仍为 ``O(n)``,但最坏需要扫描数组两遍。 三段分区 ~~~~~~~~ 单遍方法同时维护四个区间: .. code-block:: text [0, low) 已确定为 0 [low, current) 已确定为 1 [current, high] 尚未分类 (high, n) 已确定为 2 初始时前三个已分类区间为空,整个数组都是未知区。每轮只检查 ``nums[current]``,并按它的值缩小未知区。 当前值为零 ~~~~~~~~~~ 当 ``nums[current] == 0`` 时,它应进入左侧零区,因此与 ``nums[low]`` 交换。 若 ``low < current``,``nums[low]`` 来自已经确认的一区,交换到 ``current`` 后仍然已经分类;若 ``low == current``,交换等价于不变。因此交换后可以同时增加 ``low`` 和 ``current``。 当前值为一 ~~~~~~~~~~ 当 ``nums[current] == 1`` 时,它已经位于中间区域应扩展的位置,不需要交换,只增加 ``current``。 当前值为二 ~~~~~~~~~~ 当 ``nums[current] == 2`` 时,它应进入右侧二区,因此与 ``nums[high]`` 交换并减少 ``high``。 交换回来的元素来自未知区,可能是 ``0``、``1`` 或 ``2``,尚未分类。因此此时不能增加 ``current``,下一轮必须继续检查同一位置。 状态跟踪 ~~~~~~~~ 以 ``[2,0,2,1,1,0]`` 为例: .. list-table:: :header-rows: 1 * - 数组 - ``low,current,high`` - 动作 * - ``[2,0,2,1,1,0]`` - ``0,0,5`` - 当前为 2,与右端交换 * - ``[0,0,2,1,1,2]`` - ``0,0,4`` - 当前换入 0,与 ``low`` 交换 * - ``[0,0,2,1,1,2]`` - ``1,1,4`` - 当前仍为 0,继续扩大零区 * - ``[0,0,2,1,1,2]`` - ``2,2,4`` - 当前为 2,与 ``high`` 交换 * - ``[0,0,1,1,2,2]`` - ``2,2,3`` - 两个 1 依次扩大中间区 循环不变量 ~~~~~~~~~~ 每次循环前,零区、一区和二区都只包含对应颜色。三种分支分别把一个未知元素放入正确分区,并保持其他已分类区间不变。 处理 ``0`` 或 ``1`` 时 ``current`` 增加;处理 ``2`` 时 ``high`` 减少。因此未知区长度 ``high - current + 1`` 每轮严格减少。循环结束时 ``current > high``,未知区为空,三个有序分区连接成最终结果。 复杂度 ~~~~~~ 计数覆盖、两次分区和荷兰国旗算法的时间复杂度均为 ``O(n)``,额外空间均为 ``O(1)``。荷兰国旗算法只需一次分类扫描, 每个元素最多参与常数次检查或交换。