010 · Move Zeroes
My First Thoughts
初次看到这个题，第一反应可能不是算法，而是：
这个题的实际适用场景是什么？
它有点像是在做一次筛选：把某一类元素先挪开，让其他元素保持原来的顺序站到前面。
具体到这题，就是把 0 都放到数组末尾，非零元素的相对顺序不能变。
所以最直接的想法是：从左到右循环，看到 0，就把它从当前位置拿出来，再往末尾放一个 0。
如果用 Python 表达，大概会想到类似这样：
def move_zeroes(nums: list[int]) -> None:
for i, value in enumerate(nums):
if value == 0:
nums.pop(i)
nums.append(0)Why That Is Not Enough
然而 pop + append 存在问题，因为它一边遍历数组，一边改变数组本身。
这会让下标变得不稳定。
比如：
nums = [0, 0, 1]一开始 i = 0，看到第一个 0：
[0, 0, 1]
^
i执行：
nums.pop(0)
nums.append(0)数组会变成：
[0, 1, 0]注意，原来第二个 0 已经移动到了下标 0。但 for 循环下一轮会继续到 i = 1，于是它会去看 1，跳过了这个新的下标 0。
所以这种写法很容易漏掉连续的 0。
还有一个问题是，pop(i) 本身不是免费的。数组删除中间元素时，后面的元素需要整体往前移动，最坏情况下每次都是 \(O(n)\)。如果有很多个 0，整体复杂度可能会变成 \(O(n^2)\)。
这道题真正需要的不是频繁“删除 0”，而是稳定地把非零元素按顺序写到前面。
Final Idea
换一个角度看：
与其移动所有
0，不如先把所有非零元素按原顺序放到前面。
维护一个指针 write，表示：
下一个非零元素应该被写到的位置。
从左到右遍历数组：
- 如果当前数字不是
0，就把它写到nums[write]。 - 然后
write += 1，表示下一个非零元素应该放到后面一格。 - 遍历结束后，从
write到数组末尾的位置全部填成0。
比如：
nums = [0,1,0,3,12]先收集非零元素到前面：
[1,3,12,3,12]
^
write前面的 [1,3,12] 已经是正确的非零部分。后面的内容不用管它原来是什么，统一改成 0：
[1,3,12,0,0]Why It Works
write 左边的部分，始终保存着已经遇到过的所有非零元素，并且顺序和它们在原数组中的顺序一致。
当我们从左到右看到一个非零数字时，把它放到 write 的位置，就等于把它接在当前非零序列的末尾。
因为遍历方向是从左到右，所以非零元素的相对顺序不会被打乱。
遍历结束后，所有非零元素都已经放在数组前面。剩下的位置数量，刚好等于原数组里 0 的数量，所以把这些位置全部填成 0 就可以了。
Code
def move_zeroes(nums: list[int]) -> None:
write = 0
for value in nums:
if value != 0:
nums[write] = value
write += 1
for i in range(write, len(nums)):
nums[i] = 0Complexity
| Time | \(O(n)\) — 第一次遍历移动非零元素，第二次把剩余位置填成 0 |
| Space | \(O(1)\) — 只用了 write 这个额外变量 |
Takeaway
遇到“把某类元素移到末尾，同时保持其他元素相对顺序”的题，不一定要真的删除或移动那类元素。更稳定的做法通常是：把要保留顺序的元素往前写，最后把剩余位置统一处理掉。这样可以避免一边遍历一边修改数组长度带来的下标混乱。
← Quiz