移动零

LeetCode 官方题目链接

1. 题目呈现

难度等级：🟢 简单
核心考察点：数组、双指针

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

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

示例 1：

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

示例 2：

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

---

2. 解题思路拆解

方法：双指针（快慢指针）

我们需要把所有的非零元素移动到数组前面，剩下的位置补零。

1. 定义指针：
   • slow 指针：指向当前已经处理好的、非零序列的下一个存放位置。
   • fast 指针：用于遍历数组，寻找非零元素。
2. 遍历数组：
   • 让 fast 指针从头到尾遍历数组。
   • 一旦 fast 指向的元素不为 0，就将该元素赋值给 slow 指针指向的位置（nums[slow] = nums[fast]）。
   • 然后 slow 向前移动一步，准备存放下一个非零元素。
3. 补零：
   • 遍历结束后，slow 指针之前的所有位置都存放了非零元素，且顺序保持不变。
   • 从 slow 开始直到数组末尾，全部填充为 0。

这种方法只需要遍历两次数组（一次移动非零数，一次补零），或者通过交换优化为一次遍历。

---

3. 代码实现

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
    let slow = 0;
    
    // 1. 将所有非 0 元素移到前面
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            nums[slow] = nums[fast];
            slow++;
        }
    }
    
    // 2. 将剩余位置补 0
    while (slow < nums.length) {
        nums[slow] = 0;
        slow++;
    }
};

优化版（一次遍历 + 交换）

上面的方法虽然简单，但在非零元素极少的情况下（例如 [0,0,0,0,1]），会进行很多次不必要的赋值。我们可以通过交换来实现一次遍历：

var moveZeroes = function(nums) {
    let slow = 0;
    for (let fast = 0; fast < nums.length; fast++) {
        if (nums[fast] !== 0) {
            // 如果 slow 和 fast 不一样，才需要交换
            // 避免自己交换自己（例如数组开头就是非零数）
            if (slow !== fast) {
                [nums[slow], nums[fast]] = [nums[fast], nums[slow]];
            }
            slow++;
        }
    }
};

代码执行演示 (交换法)

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

1. 初始化：slow = 0, fast = 0。
2. fast=0 (0)：是 0，跳过。
3. fast=1 (1)：非 0。
   • 交换 nums[0] 和 nums[1] -> [1, 0, 0, 3, 12]。
   • slow 移至 1。
4. fast=2 (0)：是 0，跳过。
5. fast=3 (3)：非 0。
   • 交换 nums[1] 和 nums[3] -> [1, 3, 0, 0, 12]。
   • slow 移至 2。
6. fast=4 (12)：非 0。
   • 交换 nums[2] 和 nums[4] -> [1, 3, 12, 0, 0]。
   • slow 移至 3。
7. 结束。结果为 [1, 3, 12, 0, 0]。

---

4. 复杂度分析

维度	描述
时间复杂度	$O(n)$。需要遍历数组一次（或两次，取决于具体实现），$n$ 为数组长度。
空间复杂度	$O(1)$。只使用了两个指针变量，属于原地操作。