数组零值移动末尾

问题

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

要求原地操作，不能创建新数组。

// 输入
[0, 1, 0, 3, 12]

// 输出
[1, 3, 12, 0, 0]

解答

双指针法（推荐）

function moveZeroes(nums) {
  let slow = 0; // 指向下一个非零元素应该放置的位置

  // 第一次遍历：将非零元素前移
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow] = nums[fast];
      slow++;
    }
  }

  // 第二次遍历：将剩余位置填充 0
  for (let i = slow; i < nums.length; i++) {
    nums[i] = 0;
  }

  return nums;
}

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

单次遍历交换法

function moveZeroes(nums) {
  let slow = 0;

  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;
}

非原地操作（面试时说明取舍）

function moveZeroes(nums) {
  const nonZeros = nums.filter(n => n !== 0);
  const zeros = new Array(nums.length - nonZeros.length).fill(0);
  return [...nonZeros, ...zeros];
}

关键点

• 双指针：slow 记录非零元素应放置的位置，fast 遍历数组
• 原地操作的空间复杂度为 O(1)，时间复杂度为 O(n)
• 交换法只需一次遍历，但交换次数可能更多
• 非原地方法代码简洁，但空间复杂度为 O(n)
• 注意保持非零元素的相对顺序