0283.移动零

难度：🟢 简单

标签：数组、双指针

链接：283. 移动零

题目描述

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

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

示例 1:

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

示例 2:

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

解题思路

核心思想

本题的核心是在原地修改数组，将所有非零元素“向前挤”，放到数组的前面，同时保持它们的原始相对顺序。完成这个过程后，数组的剩余部分自然就应该全部填充为零。

思路选择

双指针法 是解决此问题的最优思路。我们可以使用一个指针（writePointer 或 cur）来记录下一个非零元素应该被放置的位置。

• 我们遍历整个数组，当遇到一个非零元素时，就将它放置在 writePointer 所指向的位置，然后将 writePointer 向后移动一位。

• 这个过程就像滚雪球，非零元素不断地被聚集到数组的前部。

• 遍历结束后，所有非零元素都已按顺序移动到数组前面，writePointer 指向的位置就是第一个需要被填充为零的位置。

关键步骤

1. 初始化：创建一个“写入指针” cur = 0，它表示下一个非零元素应该被写入的索引。

2. 第一次遍历：遍历整个数组 nums（使用指针 i）。 a. 如果 nums[i] 不是 0，则将其值赋给 nums[cur]。 b. 然后，将 cur 指针加一。

3. 第二次遍历：当第一次遍历结束后，cur 及其之后的所有位置都应该被置为 0。从 j = cur 开始遍历到数组末尾，将这些位置的元素都设为 0。

4. 完成：函数执行完毕，nums 数组已被原地修改。

代码实现

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function (nums) {
    // cur 指针指向下一个非零元素应该被放置的位置
    let cur = 0;

    // 第一次遍历，将所有非零元素移动到数组前面
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== 0) {
            nums[cur] = nums[i];
            cur++;
        }
    }

    // 第二次遍历，将 cur 之后的所有位置填充为 0
    for (let j = cur; j < nums.length; j++) {
        nums[j] = 0;
    }
};

复杂度分析

• 时间复杂度：O(n) 其中 n 是数组 nums 的长度。我们对数组进行了两次独立的遍历，总操作次数与 n 成正比。

• 空间复杂度：O(1) 我们只使用了常数个额外变量作为指针，操作是在原数组上进行的，空间消耗是恒定的。

相关题目

• 0027.移除元素

• 0088.合并两个有序数组

• 0026.删除有序数组中的重复项

总结

本题是双指针思想在数组原地操作问题中的一个经典应用。通过一个“慢指针”来记录有效部分的边界，一个“快指针”来探索新元素，可以高效地完成元素的筛选和移动。这种方法在很多数组问题中都有广泛的应用。