移动零

题目描述

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意，必须在不复制数组的情况下原地对数组进行操作。

示例

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

输入: nums = [0]
输出: [0]

我的解题过程

解题思路：双指针法

这道题和第 26、27 题是同一类问题，都是用双指针实现数组的原地修改。

一开始我遇到了一个问题：不知道怎么处理 0。后来想明白了，其实思路和第 27 题（移除元素）一模一样，只是多了一步——最后要把剩余位置填充 0。

具体做法：

• left 指针遍历整个数组
• right 指针记录非零元素应该放置的位置
• 遇到非零元素时，把它写入 right 位置，然后 right++
• 遇到 0 时，跳过不处理，left 继续往后走
• 最后，如果 right 的长度对应不上数组的长度，说明有零被”移除”了，需要在后面补 0

/**
 * Do not return anything, modify nums in-place instead.
 */
function moveZeroes(nums: number[]): void {
  let left = 0,
    right = 0;

  while (left < nums.length) {
    if (nums[left] !== 0) {
      nums[right] = nums[left];
      right++;
    }
    left++;
  }

  // 把剩下的位置填0
  while (right < nums.length) {
    nums[right] = 0;
    right++;
  }
}

小结

这道题本质上就是第 27 题的变体：

• 第 27 题：移除指定值，不关心后面的元素是什么
• 第 283 题：移除 0，但要求把 0 移到末尾（本质上就是把后面的位置都填成 0）

关键点在于理解：第一个循环结束后，right 的位置就是非零元素的数量。如果 right < nums.length，说明有零需要填充到后面。

掌握了双指针的这个模式，第 26、27、283 题都能用同样的思路解决。时间复杂度 O(n)，空间复杂度 O(1)。