Skip to main content

移动零

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

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

示例 1:

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

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

简单做法：分成两个数组，把非0放前一个数组，0放后一个，一次遍历分完数组后合并，时间复杂度O（n）

进阶做法(不复制数组)：一次遍历删除所有的0，并统计0的个数在后面补0，时间复杂度O（n）

双指针做法：

  1. 左指针（left）指向当前已处理的非零元素的下一个位置。
  2. 右指针（right）遍历数组，遇到非零元素时与左指针交换，并右移左指针。
  3. 遍历结束后，所有非零元素已按原顺序移至数组前部，左指针及之后的位置填充0。
function moveZeroes(nums) {
    let left = 0;
    // 第一遍遍历：将非零元素移至前部
    for (let right = 0; right < nums.length; right++) {
        if (nums[right] !== 0) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            left++;
        }
    }
    // 此时left及之后的位置可直接置为0（优化：若left之后全为0，无需操作）
    return nums;
}

代码解释：

  • 时间复杂度：O(n)，只需一次遍历。
  • 空间复杂度：O(1)，仅需常数额外空间。
  • 稳定性：非零元素的相对顺序通过交换操作保持不变。

示例过程： 输入：[0,1,0,3,12]

  1. right=1（值为1），交换left=0和right=1：[1,0,0,3,12]，left++。
  2. right=3（值为3），交换left=1和right=3：[1,3,0,0,12]，left++。
  3. right=4（值为12），交换left=2和right=4：[1,3,12,0,0]，left++。
  4. 最终结果：[1,3,12,0,0]。

进阶做法可以分为两步：删除所有0并统计删除的0的数量，然后在数组末尾补回相应数量的0。

实现方案​

function moveZeroes(nums) {
    let count = 0;
    let i = 0;
    
    // 第一遍遍历：删除所有0并统计数量
    while (i < nums.length) {
        if (nums[i] === 0) {
            nums.splice(i, 1);  // 删除当前位置的0
            count++;           // 统计删除的0的数量
        } else {
            i++;               // 非零元素，指针后移
        }
    }
    
    // 第二遍：在末尾补回相应数量的0
    for (let j = 0; j < count; j++) {
        nums.push(0);
    }
    
    return nums;
}

复杂度分析​

  • 时间复杂度：O(n²)
    每次调用 splice(i, 1) 的时间复杂度是O(n)（因为需要移动后续元素），最坏情况下需要删除所有元素，总时间为O(n²)。

  • 空间复杂度：O(1)
    仅需常数额外空间存储计数器。

与双指针法的对比​

你的方法逻辑清晰，但性能不如之前的双指针法：

  • 双指针法（时间O(n)）：通过交换操作避免了频繁移动元素，效率更高。
  • 你的方法（时间O(n²)）：splice 操作导致性能下降，尤其在处理大规模数据时。

优化建议​

如果希望保持一次遍历的思路，同时避免O(n²)的复杂度，可以改用双指针交换法（如我之前的回答），在遍历过程中直接将非零元素移到前部，而不是删除0后再补回。这样可以将时间复杂度优化到O(n)。

如果对代码性能要求不高，你的方法是简洁且正确的！