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。

这种设计让两个指针都只向右移动，天然保持了非零元素的原始相对顺序。

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。

// 优化：用 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²)，应避免

代码

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%，属于双指针入门必会的经典题目。掌握「快慢指针前缀收集器」模式后，可以快速解决一系列类似的数组操作问题。

5.1 KiB Raw Permalink Blame History Unescape Escape

04-移动零

题面

思路

方法一：快慢指针（最优 ⭐）

方法对比

代码提示

技巧

代码

5.1 KiB

Raw Permalink Blame History