LeetCode 75. 颜色分类

◎

本节目标

用荷兰国旗三指针维护 0、1、2 三段边界并原地完成一次扫描。

查看 LeetCode 原题

题意与边界

数组只包含表示三种颜色的 0、1、2，要求不用库排序，在原数组中按 0、1、2 排列。目标是一趟扫描和常数辅助空间。

三段不变量

维护 [0, left) 全是 0，[left, cur) 全是 1，(right, n) 全是 2，[cur, right] 尚未分类。当前值为 0 时与左边界交换并同时推进；为 2 时与右边界交换并只收缩 right；为 1 时只推进 cur。

正确性依据

三种操作分别把当前元素放入其最终分区，并保持已分类区间不变量。与右侧交换来的值尚未检查，所以不推进 cur；这保证未知区间不会漏元素。循环在 cur > right 时结束，未知区间为空，三个分区覆盖整个数组。

代码实现

C++

C++17

#include <utility>
#include <vector>
using namespace std;

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int left = 0;
        int cur = 0;
        int right = static_cast<int>(nums.size()) - 1;
        while (cur <= right) {
            if (nums[cur] == 0) {
                swap(nums[left], nums[cur]);
                left++;
                cur++;
            } else if (nums[cur] == 2) {
                swap(nums[cur], nums[right]);
                right--;
            } else {
                cur++;
            }
        }
    }
};

Python

Python 3

class Solution:
    def sortColors(self, nums: list[int]) -> None:
        left = 0
        cur = 0
        right = len(nums) - 1
        while cur <= right:
            if nums[cur] == 0:
                nums[left], nums[cur] = nums[cur], nums[left]
                left += 1
                cur += 1
            elif nums[cur] == 2:
                nums[cur], nums[right] = nums[right], nums[cur]
                right -= 1
            else:
                cur += 1

复杂度分析

• 时间复杂度：O(n)，每轮缩短未知区间。
• 空间复杂度：O(1)。

易错点

• 把 2 换到右侧后仍推进 cur，漏检交换回来的未知值。
• 调用通用排序，未利用只有三类值的条件。
• 区间定义含混，造成 left、cur 或 right 的边界偏一。

模式迁移

荷兰国旗划分适用于三类元素的原地分区，也是快速排序三路划分处理大量重复值的核心结构。