题目

给定一个数组 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

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

分析

问题描述

给定一个数组 nums，你需要编写一个函数，将数组中的所有 0 元素移动到数组的末尾。这个过程必须满足两个条件：

  1. 非零元素的相对顺序必须保持不变。
  2. 必须在原数组上直接进行修改（原地操作），不能创建新的数组副本。

解题思路分析

这道题的核心在于如何在移动 0 的同时，不打乱其他非零元素的原始顺序。一个直观但错误的想法是遍历数组，每当遇到一个 0，就将它与数组末尾的元素交换。这种方法的问题在于，无法保证非零元素的相对顺序。例如，[0, 1, 0, 3, 12]，如果将第一个 0 与 12 交换，数组会变成 [12, 1, 0, 3, 0]，此时 1 和 12 的相对顺序就被改变了。

因此，我们需要一种更巧妙的方法。一个非常高效且经典的的思路是 双指针法。

双指针法

我们可以把这个问题看作是将所有非零元素“向前移动”或者说“紧凑排列”，而将 0 “留在后面”。

想象一下，我们使用两个指针，一个 慢指针（slow） 和一个 快指针（fast）。

  1. slow 指针：它的作用是指向下一个应该被非零元素填充的位置。换句话说，slow 左边的所有元素（不包括 slow 自身）都应该是处理好的、按原始顺序排列的非零元素。
  2. fast 指针：它的作用是向前遍历整个数组，寻找非零元素。

算法流程如下：

  1. 初始化 slow 和 fast 两个指针，都指向数组的起始位置，即索引 0。

  2. fast 指针开始向后遍历数组（for 循环或者 while 循环）。

  3. 在遍历过程中：

    • 如果 fast 指针指向的元素 nums[fast] 不是 0：
      • 这意味着我们找到了一个需要保留顺序的非零元素。
      • 我们将这个非零元素 nums[fast] 赋值给 slow 指针指向的位置 nums[slow]。
      • 然后，将 slow 指针向后移动一位（slow++），为下一个非零元素做准备。
    • 如果 fast 指针指向的元素 nums[fast] 是 0：
      • 我们什么也不做，slow 指针保持不动。fast 指针继续向后移动，去寻找下一个非零元素。

  4. 当 fast 指针遍历完整个数组后，所有非零元素都已经被slow 指针按照原始相对顺序，紧凑地移动到了数组的前部。此时 slow 指针所在的位置，以及它之后的所有位置，都应该被填充为 0。

  5. 最后，我们从 slow 指针当前的位置开始，到数组的末尾，将所有元素都赋值为 0。

举例说明：nums = [0, 1, 0, 3, 12]

  • 初始状态: slow = 0, fast = 0

    • nums -> [0, 1, 0, 3, 12]

  • fast = 0: nums[0] 是 0。slow 不动。fast 继续。

    • slow = 0, fast = 1
    • nums -> [0, 1, 0, 3, 12]

  • fast = 1: nums[1] 是 1 (非零)。

    • 将 nums[fast] (1) 赋值给 nums[slow] (nums[0])。数组变为 [1, 1, 0, 3, 12]。
    • slow 前进, slow 变为 1。
    • slow = 1, fast = 2
    • nums -> [1, 1, 0, 3, 12]

  • fast = 2: nums[2] 是 0。slow 不动。fast 继续。

    • slow = 1, fast = 3
    • nums -> [1, 1, 0, 3, 12]

  • fast = 3: nums[3] 是 3 (非零)。

    • 将 nums[fast] (3) 赋值给 nums[slow] (nums[1])。数组变为 [1, 3, 0, 3, 12]。
    • slow 前进, slow 变为 2。
    • slow = 2, fast = 4
    • nums -> [1, 3, 0, 3, 12]

  • fast = 4: nums[4] 是 12 (非零)。

    • 将 nums[fast] (12) 赋值给 nums[slow] (nums[2])。数组变为 [1, 3, 12, 3, 12]。
    • slow 前进, slow 变为 3。
    • slow = 3, fast = 5
    • nums -> [1, 3, 12, 3, 12]

  • fast 遍历结束。此时 slow 的值为 3。这表示数组的前 3 个元素 ([0..2]) 已经是非零元素了。

  • 填充 0: 从索引 slow (3) 开始，到数组末尾，全部填充为 0。

    • nums[3] = 0
    • nums[4] = 0

  • 最终结果: nums -> [1, 3, 12, 0, 0]

这种方法只遍历了数组一次，并且是在原地操作，完全符合题目要求。

进阶思考：减少操作次数

上面的双指针法已经非常高效了，时间复杂度是 O(n)，空间复杂度是 O(1)。但我们还可以稍微优化一下赋值操作。

在上面的流程中，当非零元素本身就在它 “应该” 在的位置时（即 slow 和 fast 指针重合时），我们还是执行了 nums[slow] = nums[fast] 这样的赋值操作，这其实是多余的。比如数组 [1, 2, 3, 0, 4]，前三次遍历 slow 和 fast 始终相等，但我们还是执行了 nums[0]=1, nums[1]=2, nums[2]=3。

我们可以通过 交换 的方式来避免这种冗余操作，但这会稍微改变逻辑。

一个更直接的优化是，只有当 slow 和 fast 不在同一位置时，才进行赋值操作，并在赋值后将原 nums[fast] 位置置为0。这种思路会稍微复杂一些，但最经典的双指针解法（第一种）已经足够优秀，并且逻辑清晰，易于理解和实现，通常面试中给出第一种解法即可。我们主要还是采用第一种思路，因为它在逻辑上更像是一种“覆盖”而非“交换”，能更好地保证非零元素的相对顺序。

下面我们给出基于第一种双指针思路的 Java 代码实现。

算法复杂度分析

  • 时间复杂度: $O(n)$
    其中 $n$ 是数组 nums 的长度。快指针 fast 从头到尾完整地遍历了一次数组。填充 0 的循环也最多遍历 $n$ 次。总的操作次数与 $n$ 呈线性关系。

  • 空间复杂度: $O(1)$
    我们只使用了 slow 和 fast 两个额外的指针变量，占用的空间是常数级别的。操作是在原数组上进行的，没有使用额外的数组空间。因此空间复杂度为 $O(1)$。

答案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class Solution {
    /**
     * 使用双指针法移动零
     * @param nums 整数数组
     */
    public void moveZeroes(int[] nums) {
        // 如果数组为空或只有一个元素，无需操作
        if (nums == null || nums.length <= 1) {
            return;
        }

        // slow 指针：指向下一个非零元素应该被放置的位置
        int slow = 0;
        
        // fast 指针：遍历整个数组去寻找非零元素
        for (int fast = 0; fast < nums.length; fast++) {
            // 如果 fast 指针找到了一个非零元素
            if (nums[fast] != 0) {
                // 将这个非零元素放到 slow 指针指向的位置
                nums[slow] = nums[fast];
                // slow 指针向后移动一位
                slow++;
            }
        }

        // 当 fast 遍历完数组后，slow 指针以及其后的所有位置都应该填充为 0
        // slow 的值此时恰好是数组中非零元素的个数
        for (int i = slow; i < nums.length; i++) {
            nums[i] = 0;
        }
    }
}

// === 测试代码 ===
public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();

        // 示例 1
        int[] nums1 = {0, 1, 0, 3, 12};
        solution.moveZeroes(nums1);
        System.out.println("示例 1 输出: " + java.util.Arrays.toString(nums1)); // 期望输出: [1, 3, 12, 0, 0]

        // 示例 2
        int[] nums2 = {0};
        solution.moveZeroes(nums2);
        System.out.println("示例 2 输出: " + java.util.Arrays.toString(nums2)); // 期望输出: [0]

        // 其他测试用例
        int[] nums3 = {1, 2, 3, 4, 5};
        solution.moveZeroes(nums3);
        System.out.println("全非零测试: " + java.util.Arrays.toString(nums3)); // 期望输出: [1, 2, 3, 4, 5]

        int[] nums4 = {0, 0, 0};
        solution.moveZeroes(nums4);
        System.out.println("全零测试: " + java.util.Arrays.toString(nums4)); // 期望输出: [0, 0, 0]
    }
}