移动零

问题

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

要求原地修改数组，不能使用额外数组。

示例：

• 输入：[0, 1, 0, 3, 12]
• 输出：[1, 3, 12, 0, 0]

解答

双指针法

/**
 * 移动零到数组末尾
 * @param {number[]} nums - 输入数组
 */
function moveZeroes(nums) {
  // slow 指向下一个非零元素应该放置的位置
  let slow = 0;

  // fast 遍历数组，寻找非零元素
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // 交换 slow 和 fast 位置的元素
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow++;
    }
  }

  return nums;
}

// 测试
console.log(moveZeroes([0, 1, 0, 3, 12])); // [1, 3, 12, 0, 0]
console.log(moveZeroes([0, 0, 1]));        // [1, 0, 0]
console.log(moveZeroes([1, 2, 3]));        // [1, 2, 3]

先移动后填充

/**
 * 移动零 - 先移动非零元素，再填充零
 * @param {number[]} nums - 输入数组
 */
function moveZeroes2(nums) {
  let insertPos = 0;

  // 将非零元素依次移到前面
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== 0) {
      nums[insertPos] = nums[i];
      insertPos++;
    }
  }

  // 剩余位置填充 0
  while (insertPos < nums.length) {
    nums[insertPos] = 0;
    insertPos++;
  }

  return nums;
}

// 测试
console.log(moveZeroes2([0, 1, 0, 3, 12])); // [1, 3, 12, 0, 0]

执行过程演示

以 [0, 1, 0, 3, 12] 为例：

初始: [0, 1, 0, 3, 12], slow=0

fast=0: nums[0]=0, 跳过
fast=1: nums[1]=1, 交换 → [1, 0, 0, 3, 12], slow=1
fast=2: nums[2]=0, 跳过
fast=3: nums[3]=3, 交换 → [1, 3, 0, 0, 12], slow=2
fast=4: nums[4]=12, 交换 → [1, 3, 12, 0, 0], slow=3

结果: [1, 3, 12, 0, 0]

关键点

• 双指针：slow 记录非零元素插入位置，fast 遍历数组
• 原地交换避免额外空间，空间复杂度 O(1)
• 时间复杂度 O(n)，只需遍历一次
• 交换操作保持了非零元素的相对顺序