LeetCode 283 - 移动零（Move Zeroes）

算法刷题>LeetCode>面试经典150
2.3k words

LeetCode 283 - 移动零

问题描述

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

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

示例

示例 1:

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

示例 2:

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

约束条件

  • 1 <= nums.length <= 10^4
  • -2^31 <= nums[i] <= 2^31 - 1

进阶要求

你能尽量减少完成的操作次数吗？

解题思路

这道题的核心是双指针技巧，通过维护两个指针来实现原地操作：

核心思想

使用两个指针：

  • 慢指针（slow）：指向下一个非零元素应该放置的位置
  • 快指针（fast）：遍历整个数组，寻找非零元素

算法步骤

  1. 初始化：slow = 0，fast = 0
  2. 遍历数组：使用快指针遍历整个数组
  3. 移动非零元素：当遇到非零元素时，将其移动到慢指针位置
  4. 填充零：遍历完成后，将剩余位置填充为零

可视化过程

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
初始状态: [0,1,0,3,12]
         ↑
       slow,fast

步骤1: fast=0, nums[0]=0, 跳过
       [0,1,0,3,12]
         ↑ ↑
       slow fast

步骤2: fast=1, nums[1]=1, 移动到slow位置
       [1,1,0,3,12]
           ↑ ↑
         slow fast

步骤3: fast=2, nums[2]=0, 跳过
       [1,1,0,3,12]
           ↑   ↑
         slow fast

步骤4: fast=3, nums[3]=3, 移动到slow位置
       [1,3,0,3,12]
             ↑   ↑
           slow fast

步骤5: fast=4, nums[4]=12, 移动到slow位置
       [1,3,12,3,12]
               ↑   ↑
             slow fast

步骤6: 填充剩余位置为零
       [1,3,12,0,0]

实现细节

关键点分析

  1. 原地操作：通过双指针避免使用额外空间
  2. 保持顺序：慢指针确保非零元素按原顺序排列
  3. 效率优化：只需要一次遍历，时间复杂度为 O(n)

边界情况处理

  • 数组长度为 1：直接返回
  • 数组全为零：慢指针保持为 0
  • 数组全为非零：慢指针等于数组长度

代码实现

方法一：双指针（推荐）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public void moveZeroes(int[] nums) {
    int slow = 0; // 慢指针：指向下一个非零元素应该放置的位置
    
    // 第一遍：将所有非零元素移动到前面
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    // 第二遍：将剩余位置填充为零
    for (int i = slow; i < nums.length; i++) {
        nums[i] = 0;
    }
}

方法二：优化版本（减少操作次数）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public void moveZeroes(int[] nums) {
    int slow = 0;
    
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            // 只有当slow != fast时才进行交换，减少不必要的操作
            if (slow != fast) {
                nums[slow] = nums[fast];
                nums[fast] = 0;
            }
            slow++;
        }
    }
}

方法三：交换版本

1
2
3
4
5
6
7
8
9
10
11
12
13
public void moveZeroes(int[] nums) {
    int slow = 0;
    
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            // 交换元素
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++;
        }
    }
}

方法比较

方面 方法一（双指针） 方法二（优化版） 方法三（交换版）
时间复杂度 O(n) O(n) O(n)
空间复杂度 O(1) O(1) O(1)
操作次数 2n 最少 n
优点 逻辑清晰 操作最少 一次遍历
缺点 需要两次遍历 逻辑稍复杂 可能有不必要交换
推荐度 ★★★★☆ ★★★★★ ★★★☆☆

复杂度分析

时间复杂度

  • 方法一：$O(n)$ - 需要两次遍历数组
  • 方法二：$O(n)$ - 只需要一次遍历
  • 方法三：$O(n)$ - 只需要一次遍历

空间复杂度

所有方法的空间复杂度都是 $O(1)$，因为我们只使用了常数额外空间。

操作次数分析

对于数组 [0,1,0,3,12]：

  • 方法一：5次赋值 + 2次填充 = 7次操作
  • 方法二：3次赋值 + 2次置零 = 5次操作
  • 方法三：3次交换 = 3次操作

关键收获

核心技巧

  1. 双指针模式：一个指针遍历，一个指针维护结果位置
  2. 原地操作：通过覆盖和填充实现原地修改
  3. 保持顺序：慢指针确保元素相对顺序不变

常见陷阱

  1. 忘记填充零：第一遍遍历后需要将剩余位置置零
  2. 边界条件：处理空数组或单元素数组
  3. 不必要的操作：避免在 slow == fast 时进行无意义的赋值

相关问题

实际应用

  • 数组整理：清理数据中的无效值
  • 内存优化：压缩稀疏数组
  • 数据预处理：为后续算法准备数据

这道题是双指针技巧的经典应用，通过巧妙的指针操作实现了高效的原地数组修改，是面试中的高频题目。