347 lines
12 KiB
Markdown
347 lines
12 KiB
Markdown
|
---
|
|||
|
|
tags: [技巧, 双指针, 三向切分, 荷兰国旗, 原地排序, 数组]
|
|||
|
|
create time: 2026-05-16 18:30
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
# 98-颜色分类
|
|||
|
|
|
|||
|
|
## 题面
|
|||
|
|
|
|||
|
|
> **LeetCode 75. Sort Colors**
|
|||
|
|
|
|||
|
|
给定一个包含红色、白色和蓝色、共 `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`
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 思路
|
|||
|
|
|
|||
|
|
### 先思考一个问题 🤔
|
|||
|
|
|
|||
|
|
这个有一个经典的名字——**荷兰国旗问题（Dutch National Flag Problem）**，由 Edsger Dijkstra 提出：如何用最少交换次数把红白蓝三色球排成"红-白-蓝"的顺序？
|
|||
|
|
|
|||
|
|
> [!tip] 直觉方案
|
|||
|
|
> 统计 0、1、2 各自的个数，然后再按个数写回去——这需要两遍扫描。题目要求**一趟扫描**，怎么做？
|
|||
|
|
>
|
|||
|
|
> 排序算法如快排也能做到 $O(n \log n)$，但我们想要更好的——$O(n)$ 时间 + $O(1)$ 空间。
|
|||
|
|
|
|||
|
|
### 核心洞察：三路分区 ⭐
|
|||
|
|
|
|||
|
|
既然只有三种值 `{0, 1, 2}`，我们可以用**三个指针**把数组划分成三个区域：
|
|||
|
|
|
|||
|
|
| 区域 | 位置 | 值 | 含义 |
|
|||
|
|
|------|------|-----|------|
|
|||
|
|
| **左区 `[0, low)`** | 数组左侧 | `0` | 已经排好位的红色 |
|
|||
|
|
| **中区 `[low, mid)`** | 数组中间 | `1` | 已经排好位的白色 |
|
|||
|
|
| **未处理 `[mid, high]`** | 数组右侧 | 待确定 | 还没见过的元素 |
|
|||
|
|
| **右区 `(high, n-1]`** | 数组最右侧 | `2` | 已经排好位的蓝色 |
|
|||
|
|
|
|||
|
|
> [!question] 启发式提问
|
|||
|
|
> 如果只有一个指针从左走到右，遇到 `0` 只能放左边，遇到 `2` 只能放右边。但只靠一个指针做不到同时维护两个边界——**为什么需要三个指针？**
|
|||
|
|
>
|
|||
|
|
> 因为你需要同时知道"下一个该填 0 的位置在哪"和"下一个该填 2 的位置在哪"。这两个位置分别从两端向中间逼近。
|
|||
|
|
|
|||
|
|
### 关键性质：中区的 invariant（不变量）
|
|||
|
|
|
|||
|
|
> [!info] 不变的真理
|
|||
|
|
> 在每一步操作中，`[low, mid)` 区间内的所有元素都是 `1`。这就是说：**凡是已经被确认是 1 的元素，永远不会再被触碰**。这让算法在一趟扫描中就能完成排序。
|
|||
|
|
|
|||
|
|
### 算法流程
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
初始化：
|
|||
|
|
low = 0 → 指向下一个 0 应该放置的位置
|
|||
|
|
mid = 0 → 当前正在检查的元素
|
|||
|
|
high = n - 1 → 指向下一个 2 应该放置的位置
|
|||
|
|
|
|||
|
|
当 mid <= high 时循环：
|
|||
|
|
|
|||
|
|
情况 A: nums[mid] == 0
|
|||
|
|
将 nums[mid] 与 nums[low] 交换
|
|||
|
|
low++（左区扩大）
|
|||
|
|
mid++（当前位置已确定为 0，继续向前）
|
|||
|
|
|
|||
|
|
情况 B: nums[mid] == 1
|
|||
|
|
mid++（1 就在中区合适的位置，不动它，mid 直接前进）
|
|||
|
|
|
|||
|
|
情况 C: nums[mid] == 2
|
|||
|
|
将 nums[mid] 与 nums[high] 交换
|
|||
|
|
high--（右区扩大）
|
|||
|
|
mid 不移动！ ← 关键点
|
|||
|
|
因为从 high 换过来的元素还没有被检查过
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 最容易出错的地方
|
|||
|
|
>
|
|||
|
|
> 当 `nums[mid] == 2` 执行交换后，**mid 不能自增**。因为从 `high` 位置换过来的元素从未被检查过，需要在下一轮迭代中重新判断。
|
|||
|
|
>
|
|||
|
|
> 反之，当 `nums[mid] == 0` 执行交换后，`mid` **可以**自增——因为在交换之前 `low <= mid`，而 `nums[low]` 位置的元素要么是 `1`（在中区内），要么 `low == mid` 本身就是同一个位置。无论哪种情况，交换到 `mid` 位置的都是 `1` 或者自身，这两种都已经确认正确。
|
|||
|
|
|
|||
|
|
### 逐步跟踪演示
|
|||
|
|
|
|||
|
|
以 `nums = [2, 0, 2, 1, 1, 0]` 为例：
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
初始状态:
|
|||
|
|
索引: [0] [1] [2] [3] [4] [5]
|
|||
|
|
nums: [2, 0, 2, 1, 1, 0]
|
|||
|
|
↑ ↑ ↑
|
|||
|
|
low mid high
|
|||
|
|
|
|||
|
|
第1步: nums[mid]=2 → 与 nums[high] 交换
|
|||
|
|
索引: [0] [1] [2] [3] [4] [5]
|
|||
|
|
nums: [0, 0, 2, 1, 1, 2]
|
|||
|
|
↑ ↑ ↑
|
|||
|
|
low mid high
|
|||
|
|
（mid 不移动，重新检查 nums[mid]=0）
|
|||
|
|
|
|||
|
|
第2步: nums[mid]=0 → 与 nums[low] 交换
|
|||
|
|
索引: [0] [1] [2] [3] [4] [5]
|
|||
|
|
nums: [0, 0, 2, 1, 1, 2]
|
|||
|
|
↑ ↑ ↑
|
|||
|
|
low mid high
|
|||
|
|
（low++, mid++）
|
|||
|
|
|
|||
|
|
第3步: nums[mid]=2 → 与 nums[high] 交换
|
|||
|
|
索引: [0] [1] [2] [3] [4] [5]
|
|||
|
|
nums: [0, 0, 1, 1, 2, 2]
|
|||
|
|
↑ ↑ ↑
|
|||
|
|
low mid high
|
|||
|
|
（mid 不移动）
|
|||
|
|
|
|||
|
|
第4步: nums[mid]=1 → mid++
|
|||
|
|
索引: [0] [1] [2] [3] [4] [5]
|
|||
|
|
nums: [0, 0, 1, 1, 2, 2]
|
|||
|
|
↑ ↑ ↑
|
|||
|
|
low mid high
|
|||
|
|
|
|||
|
|
第5步: nums[mid]=1 → mid++，此时 mid > high，退出循环 ✅
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
结果：`[0, 0, 1, 1, 2, 2]` —— 排序完成！
|
|||
|
|
|
|||
|
|
### 流程图
|
|||
|
|
|
|||
|
|
```mermaid
|
|||
|
|
flowchart TD
|
|||
|
|
Start(["开始<br/>low=0 mid=0 high=n-1"]) --> Loop{"mid <= high?"}
|
|||
|
|
Loop -- 否 --> Done(["返回排序结果"])
|
|||
|
|
Loop -- 是 --> Check{"值等于多少?"}
|
|||
|
|
|
|||
|
|
Check -- "0" --> Swap0["交换 nums[low] 与 nums[mid]"]
|
|||
|
|
Swap0 --> IncBoth["low++ mid++"]
|
|||
|
|
IncBoth --> Loop
|
|||
|
|
|
|||
|
|
Check -- "1" --> IncMid["mid++"]
|
|||
|
|
IncMid --> Loop
|
|||
|
|
|
|||
|
|
Check -- "2" --> Swap2["交换 nums[mid] 与 nums[high]"]
|
|||
|
|
Swap2 --> DecHigh["high--<br/>mid 不变"]
|
|||
|
|
DecHigh --> Loop
|
|||
|
|
|
|||
|
|
style Start fill:#e3f2fd
|
|||
|
|
style Done fill:#c8e6c9
|
|||
|
|
style Swap0 fill:#fff3e0
|
|||
|
|
style Swap2 fill:#fff3e0
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 备选方案对比
|
|||
|
|
|
|||
|
|
| 方法 | 时间复杂度 | 空间复杂度 | 说明 |
|
|||
|
|
|------|----------|----------|------|
|
|||
|
|
| **三指针分区（荷兰国旗）** ⭐ | $O(n)$ | $O(1)$ | 最优解，一趟扫描 |
|
|||
|
|
| 两趟计数排序 | $O(n)$ | $O(1)$ | 统计 0/1/2 个数后回填，简单但不符合进阶要求 |
|
|||
|
|
| 快速排序的三向分区 | $O(n \log n)$ 平均 | $O(\log n)$ | 通用排序，对本题来说杀鸡用牛刀 |
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 代码提示
|
|||
|
|
|
|||
|
|
> [!abstract] 📝 Go 伪代码框架
|
|||
|
|
|
|||
|
|
```
|
|||
|
|
low, mid, high := 0, 0, len(nums)-1
|
|||
|
|
|
|||
|
|
for mid <= high:
|
|||
|
|
如果 nums[mid] == 0:
|
|||
|
|
交换 nums[low], nums[mid]
|
|||
|
|
low++
|
|||
|
|
mid++
|
|||
|
|
|
|||
|
|
否则如果 nums[mid] == 1:
|
|||
|
|
mid++
|
|||
|
|
|
|||
|
|
否则 (nums[mid] == 2):
|
|||
|
|
交换 nums[mid], nums[high]
|
|||
|
|
high--
|
|||
|
|
// mid 不变
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> [!step] 实现要点
|
|||
|
|
|
|||
|
|
1. **循环条件是 `mid <= high`**，不是 `<`，因为等于时还需要处理最后一个元素
|
|||
|
|
2. **mid 不移动的分支最容易忘**——交换完 `high` 之后必须留在原地检查新换过来的元素
|
|||
|
|
3. **Go 中没有原地 swap 运算符**，需要用临时变量：`nums[low], nums[mid] = nums[mid], nums[low]`
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 技巧
|
|||
|
|
|
|||
|
|
> [!summary] 🔑 核心模式记忆
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
// 三指针三路分区模板
|
|||
|
|
low, mid, high := 0, 0, len(nums)-1
|
|||
|
|
for mid <= high {
|
|||
|
|
switch nums[mid] {
|
|||
|
|
case 0:
|
|||
|
|
nums[low], nums[mid] = nums[mid], nums[low]
|
|||
|
|
low++
|
|||
|
|
mid++
|
|||
|
|
case 1:
|
|||
|
|
mid++
|
|||
|
|
case 2:
|
|||
|
|
nums[mid], nums[high] = nums[high], nums[mid]
|
|||
|
|
high--
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
> 看到「只有 k 种离散值的原地排序」→ 优先考虑**三路/多路分区**思想。k=3 时就是经典的荷兰国旗问题。
|
|||
|
|
|
|||
|
|
### 1. 荷兰国旗的思想本质
|
|||
|
|
|
|||
|
|
> [!quote] 💬 一句话总结
|
|||
|
|
>
|
|||
|
|
> **"小的放左边，大的放右边，中的自己站好"** ——用三个指针同时维护三个有序区域，中间的指针负责"侦察"。
|
|||
|
|
|
|||
|
|
这是一种**分区而非比较**的思维：不需要拿每个元素去跟其他元素比较大小，而是根据值域直接定位目标区域。
|
|||
|
|
|
|||
|
|
### 2. 为什么 mid 在情况 C 中不能移动？
|
|||
|
|
|
|||
|
|
> [!note] 深入理解
|
|||
|
|
>
|
|||
|
|
> 这是一个面试中几乎必问的问题。原因如下：
|
|||
|
|
>
|
|||
|
|
> `mid` 指向的是当前尚未检查的元素。当它与 `high` 交换后，`mid` 位置上得到的是来自 `high` 位置的元素——这个元素可能是 `0`、`1` 或 `2`，**从未被检查过**。如果此时 mid 自增就会漏掉这个元素，导致错误。
|
|||
|
|
>
|
|||
|
|
> 反过来看，在情况 A 中，`low <= mid`。交换前 `nums[low]` 是中区的起始位置（值为 `1`）或者 `low == mid`（自身交换）。所以交换到 `mid` 上的一定是 `1` 或自身，两种都已确认正确，mid 可以放心前进。
|
|||
|
|
|
|||
|
|
### 3. 与快速排序三向分区的联系
|
|||
|
|
|
|||
|
|
> [!info] 知识串联
|
|||
|
|
>
|
|||
|
|
> 三路分区也是快速排序优化版本的核心——当数组中存在大量重复元素时，标准快排会退化到 $O(n^2)$，而**三向快速排序**将数组分为 `< pivot`、`= pivot`、`> pivot` 三个区间，天然处理重复元素。
|
|||
|
|
>
|
|||
|
|
> 本题相当于三向分区的一个特例：pivot 的范围已知是 `{0, 1, 2}`，所以一轮扫描即可全部分清。
|
|||
|
|
|
|||
|
|
### 4. 关联变体题
|
|||
|
|
|
|||
|
|
| 题目 | 变化点 | 核心思路 |
|
|||
|
|
|------|--------|---------|
|
|||
|
|
| **75. Sort Colors** | 三种离散值排序 | 三指针荷兰国旗 ✅ |
|
|||
|
|
| **912. Sort an Array** | 通用数组排序 | 归并排序 / 堆排序 / 三向快排 |
|
|||
|
|
| **三向快排（快排优化）** | 含大量重复元素 | Dutch Partitioning 作为 partition 步骤 |
|
|||
|
|
|
|||
|
|
### 5. Go 运行细节
|
|||
|
|
|
|||
|
|
> [!example] 🐹 Go 特有注意事项
|
|||
|
|
|
|||
|
|
- Go 原生支持**并行赋值**，一行即可完成 swap：`a, b = b, a`，无需临时变量
|
|||
|
|
- 当数组长度为 1 时，`low == mid == high`，循环进入一次后退出，逻辑正确
|
|||
|
|
- `switch` 语句在 Go 中比多个 `if-else` 更清晰，也稍快（编译器生成跳转表）
|
|||
|
|
|
|||
|
|
---
|
|||
|
|
|
|||
|
|
## 代码
|
|||
|
|
|
|||
|
|
```go
|
|||
|
|
// sortColors sorts an array of 0s, 1s, and 2s in-place using
|
|||
|
|
// the Dutch National Flag three-pointer approach.
|
|||
|
|
// All 0s come first, then all 1s, then all 2s.
|
|||
|
|
func sortColors(nums []int) {
|
|||
|
|
// ── Step 1: 初始化三个指针 ──
|
|||
|
|
// low: 下一个 0 应该放置的位置（左区右边界）
|
|||
|
|
// mid: 当前正在检查的元素（侦察指针）
|
|||
|
|
// high: 下一个 2 应该放置的位置（右区左边界）
|
|||
|
|
low, mid, high := 0, 0, len(nums)-1
|
|||
|
|
|
|||
|
|
// ── Step 2: 一趟扫描分区 ──
|
|||
|
|
for mid <= high {
|
|||
|
|
switch nums[mid] {
|
|||
|
|
case 0:
|
|||
|
|
// 遇到 0：交换到左区
|
|||
|
|
// 交换后 mid 位置的元素已确认为 1 或自身，mid 可以前进
|
|||
|
|
nums[low], nums[mid] = nums[mid], nums[low]
|
|||
|
|
low++
|
|||
|
|
mid++
|
|||
|
|
|
|||
|
|
case 1:
|
|||
|
|
// 遇到 1：留在中区，mid 直接前进
|
|||
|
|
mid++
|
|||
|
|
|
|||
|
|
case 2:
|
|||
|
|
// 遇到 2：交换到右区
|
|||
|
|
// 注意 mid 不能前进！因为从 high 换过来的元素还未被检查
|
|||
|
|
nums[mid], nums[high] = nums[high], nums[mid]
|
|||
|
|
high--
|
|||
|
|
}
|
|||
|
|
}
|
|||
|
|
|
|||
|
|
// ── Step 3: 隐式结束 ──
|
|||
|
|
// 当 mid > high 时，整个数组已被划分为 [0]*[1]*[2]* 三段
|
|||
|
|
}
|
|||
|
|
```
|
|||
|
|
|
|||
|
|
### 代码走读
|
|||
|
|
|
|||
|
|
> [!success] ✅ 复杂度总结
|
|||
|
|
|
|||
|
|
| 指标 | 结果 | 说明 |
|
|||
|
|
|------|------|------|
|
|||
|
|
| **时间复杂度** | $O(n)$ | 每个元素最多被访问常数次（`mid++` 走 n 步；每次交换至少消耗一个 `low` 或 `high`，最多 n 次交换） |
|
|||
|
|
| **空间复杂度** | $O(1)$ | 仅使用了三个整型变量 `low`、`mid`、`high` |
|
|||
|
|
|
|||
|
|
完美满足一趟扫描 + 常数空间的进阶要求！
|
|||
|
|
|
|||
|
|
> [!quote] 💬 面试建议
|
|||
|
|
|
|||
|
|
这道题是考察**双指针/分区思想**的经典题。面试中被问到后：
|
|||
|
|
|
|||
|
|
1. **先确认约束条件**——只有三种值、原地排序、一趟扫描最优
|
|||
|
|
2. **引出荷兰国旗问题**——说出名字会给面试官留下好印象
|
|||
|
|
3. **画示意图解释三路分区**——标出 low/mid/high 三个指针的职责和不变量
|
|||
|
|
4. **解释 mid 在不同情况下的行为差异**——这是展示你思考深度的地方
|
|||
|
|
5. **主动分析时间复杂度**——证明每个元素只被常数次访问
|
|||
|
|
|
|||
|
|
> [!warning] ⚠️ 常见陷阱
|
|||
|
|
|
|||
|
|
> 1. **mid 在交换 `high` 后忘记停留**——最常见的 bug，会导致漏检元素
|
|||
|
|
> 2. **循环条件写成 `mid < high`**——等于时仍需处理最后一个元素
|
|||
|
|
> 3. **误以为 `low++` 放在 `case 2` 中也正确**——`low` 只对应 `0` 的位置，与 `2` 无关
|
|||
|
|
> 4. **忽略空数组边界**——虽然题目保证了 `n >= 1`，但在实际工程中应加防御性检查
|