【LeetCode热题100道笔记+动画】移动零

题目描述

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

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

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

示例 2:
输入: nums = [0]
输出: [0]

提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

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

思考

题目要求原地算法，不能借助额外的空间。那么只能通过数组元素交换位置实现把 0 都挪到最后面。遍历数组时要找到第一个 0 的位置，索引记为 firstZeroIndex，firstZeroIndex 初始化为 -1 表示还没有找到第一个 0。后续遍历元素 nums[i] 只要非 0 并且 firstZeroIndex 不为 -1，那就交换 nums[i] 和 nums[firstZeroIndex]，这样等于把 0 后面第一个非 0 元素 nums[i] 移到 0 前面去了，那么交换后 firstZeroIndex 位置处已经不是第一个 0 了，只要执行 firstZeroIndex++，它将指向新的第一个 0 的位置，为什么要会这样？因为在寻找用于交换的非 0 的元素 nums[i] 时遇到后续的 0 都直接跳过，所以开区间 (firstZeroIndex, i] 中的元素都是 0，firstZeroIndex++ 是开区间中的第一个 0 元素。当更新完 firstZeroIndex 后，完成一轮循环逻辑，firstZeroIndex 是循环不变量。整个过程遍历一遍数组，时间复杂度 $O(n)$，空间复杂度 $O(1)$。本题考察的是双指针解题思路。

算法过程

1. 初始化指针：定义 firstZeroIndex 为 -1，用于标记当前第一个 0 的位置（未找到时为 -1）。
2. 遍历数组：
   • 若遇到 0 且 firstZeroIndex 为 -1，更新 firstZeroIndex 为当前索引（记录首个 0 的位置）。
   • 若遇到非 0 且 firstZeroIndex 不为 -1（已找到首个 0）：
     • 交换当前元素与 firstZeroIndex 位置的 0，将非 0 元素移至前面。
     • firstZeroIndex 加 1，指向交换后新的首个 0 的位置。
3. 终止状态：遍历结束后，所有非 0 元素已按原顺序移至数组前部，0 全部集中在末尾。

该过程通过一次遍历完成，时间复杂度 $O(n)$，空间复杂度 $O(1)$，且操作次数最少（仅非 0 元素与 0 交换）。

代码

/**
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var moveZeroes = function(nums) {
   
   
    let firstZeroIndex = -1;
    for (let i = 0; i < nums.length; i++) {
   
   
        if (nums[i] === 0) {
   
   
            if (firstZeroIndex === -1) {
   
   
                firstZeroIndex = i;