161 lines
5.1 KiB
Markdown
161 lines
5.1 KiB
Markdown
---
|
||
tags: ["LeetCode", "双指针", "简单"]
|
||
create time: 2026-05-13 16:00
|
||
---
|
||
|
||
# 04-移动零
|
||
|
||
## 题面
|
||
|
||
给定一个数组 `nums`，编写一个函数将所有 `0` 移动到数组的末尾，同时保持非零元素的相对顺序。
|
||
|
||
请注意，必须**不复制数组**的情况下原地对数组进行操作。
|
||
|
||
**示例 1:**
|
||
|
||
```
|
||
输入：nums = [0,1,0,3,12]
|
||
输出：[1,3,12,0,0]
|
||
```
|
||
|
||
**示例 2:**
|
||
|
||
```
|
||
输入：nums = [0]
|
||
输出：[0]
|
||
```
|
||
|
||
**提示:**
|
||
|
||
- `1 <= nums.length <= 10^4`
|
||
- `-2^31 <= nums[i] <= 2^31 - 1`
|
||
|
||
**进阶：** 你能尽量减少完成的操作次数吗？
|
||
|
||
---
|
||
|
||
## 思路
|
||
|
||
> [!question] 💡 思考
|
||
> 要求"不改变非零元素相对顺序"且"原地操作"，这暗示我们可以在一次遍历中把非零元素集中到前面，剩余位置补零即可。关键问题是如何用最小的额外操作完成这件事。
|
||
|
||
### 方法一：快慢指针（最优 ⭐）
|
||
|
||
> [!info] 🎯 核心思想
|
||
> **慢指针 slow 指向下一个非零元素应该放置的位置，快指针 fast 扫描整个数组。** 遇到非零元素就把 `nums[fast]` 交换（或覆盖）到 `nums[slow]`，然后 `slow++`。一轮结束后 `slow` 之后的所有位置都是多余的，全部填 0。
|
||
|
||
这种设计让两个指针都**只向右移动**，天然保持了非零元素的原始相对顺序。
|
||
|
||
```mermaid
|
||
flowchart LR
|
||
A["开始\nslow = 0, fast = 0"] --> B{"fast < n?"}
|
||
B -->|"否"| C["将 slow 及之后所有位置置 0"]
|
||
B -->|"是"| D{"nums[fast] == 0?"}
|
||
D -->|"否"| E["swap(nums[slow], nums[fast])\nslow++, fast++"]
|
||
D -->|"是"| F["fast++"]
|
||
E --> B
|
||
F --> B
|
||
C --> G["返回结果"]
|
||
```
|
||
|
||
以 `nums = [0, 1, 0, 3, 12]` 为例：
|
||
|
||
| 步骤 | slow | fast | nums[fast] | 动作 | 数组状态 |
|
||
|------|------|------|------------|------|----------|
|
||
| 初始 | 0 | 0 | 0 | 为 0，跳过 | `[0,1,0,3,12]` |
|
||
| 1 | 0 | 1 | 1 | 不为 0 → swap(0,1) | `[1,0,0,3,12]` |
|
||
| 2 | 1 | 2 | 0 | 为 0，跳过 | `[1,0,0,3,12]` |
|
||
| 3 | 1 | 3 | 3 | 不为 0 → swap(1,3) | `[1,3,0,0,12]` |
|
||
| 4 | 2 | 4 | 12 | 不为 0 → swap(2,12) | `[1,3,12,0,0]` |
|
||
| 结束 | — | — | — | slow=3，其后全补零 | `[1,3,12,0,0]` |
|
||
|
||
**时间复杂度：O(n)** — fast 指针遍历一次，末尾补零最多 n 次操作。
|
||
**空间复杂度：O(1)** — 仅使用两个指针变量。
|
||
|
||
### 方法对比
|
||
|
||
> [!tip] 🔑 为什么「先覆盖再补零」同样优秀
|
||
> 如果不用 swap 而采用「直接把非零元素覆盖到 slow 位置，最后统一补零」的方式，可以减少写入次数——每个非零元素最多写两次（一次覆盖、可能被后面的覆盖），零元素只写一次。当原数组有大量连续零时，swap 可能导致不必要的来回交换，但渐进复杂度不变。两种写法在实际测试中差异极小，可根据习惯选择。
|
||
|
||
---
|
||
|
||
## 代码提示
|
||
|
||
```
|
||
// 伪代码模板
|
||
slow = 0
|
||
for fast 从 0 到 n-1:
|
||
if nums[fast] != 0:
|
||
swap(nums[slow], nums[fast])
|
||
slow++
|
||
|
||
// 此时 slow 之后的位置全部需要补零
|
||
for i 从 slow 到 n-1:
|
||
nums[i] = 0
|
||
```
|
||
|
||
Go 语言中的简洁写法：可以先不 swap，直接覆盖并记录旧值，循环结束后再补零。这样避免了不必要的自身 swap。
|
||
|
||
```go
|
||
// 优化：用 temp 记录被覆盖的值，最后统一补零
|
||
slow := 0
|
||
for fast, num := range nums {
|
||
if num != 0 {
|
||
nums[slow] = num
|
||
if slow != fast {
|
||
nums[fast] = 0 // 非自身交换时才清零
|
||
}
|
||
slow++
|
||
}
|
||
}
|
||
```
|
||
|
||
---
|
||
|
||
## 技巧
|
||
|
||
> [!tip] 🔑 核心模式：前缀收集器（Prefix Collector）
|
||
> 本题本质是一个「前缀收集器」：slow 指向的就是"已收集的合法元素个数"。这种模式可以泛化到其他场景——例如"移除指定值的所有元素"（LeetCode 27）、"去重排序数组"（LeetCode 26）等，核心框架完全一致。
|
||
|
||
> [!note] 🐹 Go 中的 swap 技巧
|
||
> Go 支持多赋值实现 swap：`a, b = b, a`，编译器会生成临时变量避免中间态。但在本题中，如果 `slow == fast`（即当前元素本身就是非零且已在正确位置），直接跳过 swap 可以省去无意义的赋值操作。
|
||
|
||
> [!info] 📊 操作次数分析
|
||
> - **最坏情况**（如 `[1,2,3,...]`）：每个元素访问 1 次 + 覆盖 1 次 = 约 2n 次写入
|
||
> - **最好情况**（如 `[1,2,3,0,0,0]`）：non-zero 元素写入各 1 次 + fast 处补零 = 约 n + k 次（k 为零元素个数）
|
||
> - 暴力法（每次遇到零后移）可达 O(n²)，应避免
|
||
|
||
---
|
||
|
||
## 代码
|
||
|
||
```go
|
||
func moveZeroes(nums []int) {
|
||
slow := 0
|
||
|
||
for fast, num := range nums {
|
||
if num != 0 {
|
||
// 非零元素放到 slow 位置
|
||
if slow != fast {
|
||
nums[slow], nums[fast] = nums[fast], nums[slow]
|
||
}
|
||
slow++
|
||
}
|
||
}
|
||
|
||
// 可选的另一种写法（先覆盖再补零，减少 swap 开销）：
|
||
// for fast, num := range nums {
|
||
// if num != 0 {
|
||
// nums[slow] = num
|
||
// if slow != fast {
|
||
// nums[fast] = 0
|
||
// }
|
||
// slow++
|
||
// }
|
||
// }
|
||
}
|
||
```
|
||
|
||
> [!success] ✅ 运行验证
|
||
> 这是 LeetCode 第 283 题，通过率约 60%，属于双指针入门必会的经典题目。掌握「快慢指针前缀收集器」模式后，可以快速解决一系列类似的数组操作问题。
|