Move Zeroes
你会得到一个整数数组 nums。把所有 0 移到数组末尾，并保持其他值的原有顺序。返回重排后的数组，其长度与 nums 相同。
函数
- numsinteger-array
- 需要重新排列的整数数组
- 返回值integer-array
- nums 中先放非零值，并保持原有顺序，最后放置所有 0
约束条件
1 ≤ nums.length ≤ 5000-105 ≤ nums[i] ≤ 105
示例
- 输入
- nums = [0, 4, 0, 7, 2]
- 输出
- [4, 7, 2, 0, 0]
- 解释
- 不为 0 的值是 4、7 和 2，它们按原来的顺序排在前面。两个 0 填在最后两个位置。
- 输入
- nums = [-3, 8, 1]
- 输出
- [-3, 8, 1]
- 解释
- 没有 0 可以移动，因此数组保持不变。-3 是负数，不是 0，所以它仍然排在最前面。
- 输入
- nums = [0]
- 输出
- [0]
- 解释
- 只包含一个 0 的数组已经是最终形状。
进阶
你能否只遍历一次，把每个 0 移到最前面，同时保持其他值的顺序不变，并且只使用 O(1) 的额外内存？
提示
逐个打开提示，每个都会多透露一点。
想象一下最终的数组：非零值保持原来的顺序，后面接着零。你遇到的第一个非零值最终应该放在哪里？
在前面保留一个索引
write，指向下一个空位。遇到的每个非零值都放在这个位置，然后将位置向右移动一格。用第二个索引
read遍历。当nums[read]不为 0 时，将它与nums[write]交换，并让write向前移动。两个索引之间的所有值始终为 0，因此每次交换都会将一个 0 向后移，同时保持其他值的顺序。
题解
约束条件是保持其他值的原始顺序，因此不能将每个 0 都与最后一个元素交换。一个索引读取每个元素，另一个索引标记下一个非零值应放置的位置，只需遍历一遍，就能原地完成操作。
复制非零值
思路
按遇到的顺序，将每个非零值复制到一个新数组中，然后添加零，直到它的长度与 nums 一样。顺序是正确的，因为你按照读取的顺序复制值。
每个元素只读取一次、写入一次：时间复杂度为 O(n)，另外第二个数组需要 O(n) 的内存。
算法
- 创建一个空的结果数组。
- 遍历
nums中的每个值，如果它不是 0，就将它添加到结果中。 - 添加 0，直到结果中的元素数量与
nums相同。 - 返回结果。
def moveZeroes(nums):
result = [x for x in nums if x != 0]
result += [0] * (len(nums) - len(result))
return result双指针，原地交换
思路
每一步之后，都会满足两个事实：write 之前的所有元素，按顺序都是目前为止遇到的非零值；从 write 到 read 之间的所有元素都是 0。非零的 nums[read] 会与 nums[write] 交换，因此交换后 read 位置上的值是 0；如果两个索引相等，则该位置上的值不变。非零值只会越过 0，不会互相越过，所以它们的顺序保持不变。
对于 [0, 4, 0, 7, 2]，4、7 和 2 依次交换到索引 0、1 和 2，0 最后位于索引 3 和 4。只需遍历一遍，也不需要第二个数组：时间复杂度为 O(n)，空间复杂度为 O(1)。
算法
- 将
write设为 0。 - 将
read从第一个索引移到最后一个索引。 - 如果
nums[read]不为 0，就将nums[read]与nums[write]交换，然后将write加 1。 - 返回
nums。
def moveZeroes(nums):
write = 0 # nums[:write] holds the non-zero values found so far, in order
for read in range(len(nums)):
if nums[read] != 0:
nums[write], nums[read] = nums[read], nums[write]
write += 1
return nums
易错点和边界情况
- 将每个 0 与最后一个元素交换。这样虽然移动了 0，却打乱了其余元素：
[0, 4, 7]会变成[7, 4, 0]。 - 遍历数组时删除 0。在
[0, 0, 5]中，删除索引 0 处的元素后，第二个 0 会移到索引 0，而循环会继续移动到索引 1。每次删除都会移动数组中的其余元素，这会让循环的时间复杂度变成O(n²)。 - 测试
x > 0，而不是x != 0。负值不是 0：[-1, 0, -2]必须变成[-1, -2, 0]，但复制版本会返回[0, 0, 0]。
常见问题3
移动零的时间复杂度是多少？
O(n)：两种方法都会读取每个元素一次。将非零值复制到新数组需要 O(n) 的额外内存，而双指针交换在数组内部进行，只需要 O(1) 的额外内存。
能否用更少的写入操作完成“移动零”挑战？
是的。不要交换，而是将每个非零值复制到 nums[write]，扫描完成后，将从 write 到末尾的每个位置都填上 0。这样每个位置最多只会写入一次。当 read 等于 write 时，也可以跳过交换，因为交换只会把值放回原来的位置。
为什么 Move Zeroes 是一道双指针问题？
一个指针读取每个元素，另一个标记已处理部分的末尾。它们都只向前移动，因此合起来只需遍历一次。同样的读写模式可以从排序数组中删除重复项，也可以原地从数组中过滤掉任意值。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def moveZeroes(nums):
# 在这里编写代码测试 #1
测试 #2
测试 #3
参数
nums = [0, 4, 0, 7, 2]
预期输出
[4, 7, 2, 0, 0]