华为 OD 训练营 · 题解精讲
LC283. 移动零
LC283. 移动零
题目描述
给定一个数组 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 进阶：你能尽量减少完成的操作次数吗？
题目解析
解题思路
本题要求原地将数组中的零移动到末尾，同时保持非零元素的相对顺序。参考代码采用双指针（快慢指针） 技巧，核心思路是：用慢指针 slow 标记当前已处理好的非零元素的下一个位置，用快指针 fast 遍历整个数组。当遇到非零元素时，将其覆盖到 slow 指向的位置，然后 slow 后移一位。遍历结束后，slow 之后的所有位置都置为零。
关键步骤
1. 初始化慢指针：slow = 0，表示第一个可能被零占据的位置。 2. 快指针遍历：fast 从 0 到 len(nums)-1：
- 若
nums[fast] != 0，将其赋值给nums[slow]，然后slow += 1。 - 若
nums[fast] == 0，跳过，不操作。
3. 填充零：从 slow 到数组末尾，将所有元素置为 0。
示意图（以 [0,1,0,3,12] 为例）：
初始: [0, 1, 0, 3, 12] slow=0, fast=0
fast=0: nums[0]==0 → 跳过
fast=1: nums[1]!=0 → nums[0]=1, slow=1 → [1,1,0,3,12]
fast=2: nums[2]==0 → 跳过
fast=3: nums[3]!=0 → nums[1]=3, slow=2 → [1,3,0,3,12]
fast=4: nums[4]!=0 → nums[2]=12, slow=3 → [1,3,12,3,12]
最后: 从 slow=3 开始置零 → [1,3,12,0,0]复杂度分析
- 时间复杂度：O(n)，其中 n 为数组长度。快指针遍历一次（O(n)），慢指针后的置零循环最多也遍历一次（O(n)），总体为 O(2n) = O(n)。
- 空间复杂度：O(1)，只使用了
slow、fast等常数个变量。
参考代码
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
# 设置一个变量，用来指向经过一系列操作后数组中所有为 0 元素的第一个位置上
# 一开始默认在索引为 0 的位置
slow = 0
# 从头到尾遍历数组
# 遍历完毕之后，slow 指向了一个为 0 的元素，或者如果数组中不存在 0 ，就和 fast 一样，超过了数组的范围
for fast in range(len(nums)) :
# 在遍历过程中，如果发现访问的元素是非 0 元素
# 说明 slow 不在正确的位置上，需要向后移动，寻找合适的位置
if nums[fast] != 0:
# 这个时候，原先 slow 的值需要被 fast 的值覆盖
nums[slow] = nums[fast]
# slow 需要向后移动，寻找合适的位置
slow += 1
# 接下来，只需要把 slow 极其后面所有的元素都设置为 0 就行
for i in range(slow,len(nums)) :
# 都设置为 0
nums[i] = 0
四、复杂度分析
时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。
空间复杂度：O(1)。只需要常数的空间存放若干变量。