LeetCode 283. 移动零

整体思路

将一个整数数组中的所有零元素移动到数组的末尾，同时保持所有非零元素的原始相对顺序。此操作要求在原数组上直接进行修改（in-place），而不创建新的数组副本。

主要算法步骤如下：

1. 双指针法 (Fast-Slow Pointers)：代码采用了双指针的策略。r（right pointer）作为快指针，负责从头到尾遍历整个数组；l（left pointer）作为慢指针，其核心作用是标记下一个非零元素应该被放置的位置。
2. 一次遍历，完成非零元素的迁移：
   • 快指针 r 负责扫描数组。当 nums[r] 遇到的元素 不是零 时，就将其值“搬运”到慢指针 l 指向的位置 nums[l]。
   • 每当一次成功的搬运（即 nums[l] = nums[r]）完成后，慢指针 l 向前移动一位 (l++)，为下一个非零元素准备好位置。
   • 如果 nums[r] 遇到的元素是零，则快指针 r 继续前进，而慢指针 l 保持不动，这相当于“跳过”了零元素，等待下一个非零元素的到来。
3. 收尾：填充剩余部分为零：
   • 当第一个循环（由快指针 r 控制）结束后，所有非零元素都已按照原始相对顺序被紧凑地移动到了数组的前部，其范围是 [0, l-1]。
   • 此时，慢指针 l 指向的位置就是第一个应该被填充为零的位置。
   • 第二个 while 循环从 l 开始，将数组剩余的所有位置都高效地填充为零，直到数组末尾。

这种方法非常巧妙且高效，因为它仅通过一次完整的遍历就完成了所有非零元素的重新排列，并且是在常数级别的额外空间内完成的。

完整代码

class Solution {
    public void moveZeroes(int[] nums) {
        // 定义慢指针 l，它指向下一个非零元素应该被放置的位置。
        // 也可以理解为，[0, l-1] 区间内都是已处理好的、按原序排列的非零元素。
        int l = 0; 
        
        // 获取数组的长度，用于确定循环边界，是一种常见的优化。
        int n = nums.length;
        
        // 使用快指针 r 遍历整个数组，从索引 0 到 n-1。
        for (int r = 0; r < n; r++) {
            // 如果快指针 r 遇到的元素是 0，则不做任何操作，直接跳过，继续下一次循环。
            if (nums[r] == 0) {
                continue;
            }
            
            // 如果快指针 r 遇到的元素不是 0，则将其值赋给慢指针 l 指向的位置。
            // 这一步完成了非零元素的“前移”，保持了它们的相对顺序。
            // 赋值完成后，慢指针 l 前进一位，为下一个非零元素准备空间。
            nums[l++] = nums[r];
        }
        
        // 经过第一个循环后，所有非零元素都已移动到数组的前部，
        // 且 l 指向了第一个需要被置为 0 的位置。
        // 这个循环将数组从 l 到末尾的所有位置都填充为 0。
        while (l < n) {
            nums[l++] = 0;
        }
    }
}

时空复杂度

• 时间复杂度：O(n)

  • 计算依据：该算法包含两个独立的、非嵌套的循环，其中 n 是输入数组 nums 的长度。
    1. 第一个 for 循环由快指针 r 控制，它从 0 到 n-1 完整地遍历了一遍数组。循环体内的操作（判断和赋值）都是常数时间 O(1) 的。因此，这个循环的时间复杂度是 O(n)。
    2. 第二个 while 循环由慢指针 l 控制。它负责填充数组尾部的零。在整个算法的执行过程中，l 指针是单调递增的，从 0 最多移动到 n。
  • 总体分析：虽然有两个循环，但它们是顺序执行的。快指针 r 遍历了 n 个元素。慢指针 l 在两个循环中总共也只会从 0 移动到 n。每个数组元素最多被读取一次（由 r 指针）和写入一到两次。因此，总的操作次数与数组的长度 n 成线性关系。所以，最终时间复杂度为 O(n)。

• 空间复杂度：O(1)

  • 计算依据：该算法是在 in-place（原地） 完成操作的。它没有使用任何与输入数组大小 n 相关的额外数据结构（例如，没有创建新的数组或哈希表来辅助计算）。
  • 算法只使用了几个固定数量的变量（l, n, r），这些变量所占用的内存空间是固定的，不随输入数组 n 的规模而增长。因此，额外空间复杂度是常数级别的。所以，最终空间复杂度为 O(1)。