跳到主要内容

移动零

问题​

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

要求：

  • 必须在原数组上操作，不能拷贝额外的数组
  • 尽量减少操作次数

示例：

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

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

来源：LeetCode 283. 移动零

答案​

解法一：双指针（推荐）​

使用快慢双指针，快指针遍历数组，慢指针指向下一个非零元素应该放置的位置。

moveZeroes.ts
function moveZeroes(nums: number[]): void {
  let slow = 0; // 慢指针：指向下一个非零元素应该放置的位置

  // 快指针遍历数组
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // 遇到非零元素，放到 slow 位置
      nums[slow] = nums[fast];
      slow++;
    }
  }

  // slow 之后的位置全部填充 0
  for (let i = slow; i < nums.length; i++) {
    nums[i] = 0;
  }
}

执行过程演示：

nums = [0, 1, 0, 3, 12]

初始: slow = 0

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

第一轮后: [1, 3, 12, 3, 12], slow = 3

填充 0: nums[3] = 0, nums[4] = 0

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

解法二：双指针交换（一次遍历）​

优化版本：遇到非零元素时直接与慢指针位置交换，只需一次遍历。

moveZeroesSwap.ts
function moveZeroes(nums: number[]): void {
  let slow = 0;

  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      // 交换 fast 和 slow 位置的元素
      if (fast !== slow) {
        [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      }
      slow++;
    }
  }
}
为什么要判断 fast !== slow？

当 fast === slow 时，说明当前位置就是非零元素应该在的位置，不需要交换。这个判断可以减少不必要的交换操作。

解法三：冒泡思想（不推荐）​

类似冒泡排序，每次将 0 "冒泡"到末尾。虽然直观但效率较低。

moveZeroesBubble.ts
function moveZeroes(nums: number[]): void {
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < nums.length - 1 - i; j++) {
      if (nums[j] === 0 && nums[j + 1] !== 0) {
        [nums[j], nums[j + 1]] = [nums[j + 1], nums[j]];
      }
    }
  }
}
注意

冒泡解法时间复杂度为 O(n2)O(n^2)，面试中不推荐使用，但可以作为优化前的对比方案展示。

复杂度分析​

解法时间复杂度空间复杂度说明
双指针（两次遍历）O(n)O(n)O(1)O(1)第一次移动非零，第二次填充零
双指针交换O(n)O(n)O(1)O(1)一次遍历完成，推荐
冒泡O(n2)O(n^2)O(1)O(1)效率低，不推荐

图解双指针过程​

变体题目​

变体 1：移动零到数组开头
function moveZeroesToFront(nums: number[]): void {
  let slow = nums.length - 1;

  for (let fast = nums.length - 1; fast >= 0; fast--) {
    if (nums[fast] !== 0) {
      if (fast !== slow) {
        [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      }
      slow--;
    }
  }
}

// [0, 1, 0, 3, 12] => [0, 0, 1, 3, 12]
变体 2：移动特定值到末尾
function moveValue(nums: number[], val: number): void {
  let slow = 0;

  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      if (fast !== slow) {
        [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      }
      slow++;
    }
  }
}

// moveValue([1, 2, 2, 3, 2], 2) => [1, 3, 2, 2, 2]

常见面试问题​

Q1: 为什么双指针解法的时间复杂度是 O(n)O(n)？​

答案：

虽然有两个指针，但它们都只遍历数组一次：

  • fast 指针从头走到尾，遍历 n 次
  • slow 指针只会前进，不会后退，最多移动 n 次
  • 总操作次数 ≤ 2n，所以时间复杂度是 O(n)O(n)
// fast 每次循环移动一次
for (let fast = 0; fast < nums.length; fast++) {
  if (nums[fast] !== 0) {
    nums[slow] = nums[fast];
    slow++;  // slow 只在非零时才移动
  }
}

Q2: 双指针的两种写法（覆盖 vs 交换）有什么区别？​

答案：

// 写法一：覆盖（两次遍历）
function moveZeroes1(nums: number[]): void {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      nums[slow++] = nums[fast];  // 覆盖
    }
  }
  while (slow < nums.length) {
    nums[slow++] = 0;  // 填充零
  }
}

// 写法二：交换（一次遍历）
function moveZeroes2(nums: number[]): void {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];  // 交换
      slow++;
    }
  }
}
写法遍历次数写操作次数特点
覆盖2较多逻辑清晰
交换1较少效率更高

Q3: 这道题和"移除元素"有什么关系？​

答案：

LeetCode 27. 移除元素 是"移动零"的泛化版本：

// 移除元素：移除所有等于 val 的元素，返回剩余长度
function removeElement(nums: number[], val: number): number {
  let slow = 0;
  for (let fast = 0; fast < nums.length; fast++) {
    if (nums[fast] !== val) {
      nums[slow++] = nums[fast];
    }
  }
  return slow;  // 返回新长度
}

// 移动零 = 移除0 + 在末尾补0
function moveZeroes(nums: number[]): void {
  const newLen = removeElement(nums, 0);
  for (let i = newLen; i < nums.length; i++) {
    nums[i] = 0;
  }
}

Q4: 如果要求移动零到数组开头，怎么修改？​

答案：

反向遍历即可：

function moveZeroesToFront(nums: number[]): void {
  let slow = nums.length - 1;

  for (let fast = nums.length - 1; fast >= 0; fast--) {
    if (nums[fast] !== 0) {
      [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
      slow--;
    }
  }
}

// [0, 1, 0, 3, 12] => [0, 0, 1, 3, 12]

Q5: 为什么交换写法要判断 fast !== slow？​

答案：

if (nums[fast] !== 0) {
  if (fast !== slow) {  // 这个判断有必要吗？
    [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
  }
  slow++;
}

原因：当 fast === slow 时，说明到目前为止没有遇到零，当前元素本来就在正确位置，自己和自己交换是无意义的操作。

不加这个判断也能得到正确结果，但会有多余的赋值操作：

  • 数组 [1, 2, 3]：不加判断会做 3 次自交换
  • 数组 [0, 0, 1]：加不加判断效果一样

结论：这是一个性能优化，可以减少不必要的写操作。

面试要点总结
  1. 首选双指针交换解法：一次遍历，O(n)O(n) 时间，O(1)O(1) 空间
  2. 理解双指针的含义：slow 指向"已处理区域的末尾"，fast 负责探索
  3. 能够手写执行过程：面试官可能要求手动模拟
  4. 了解变体：移动到开头、移动特定值等

相关链接​