LeetCode 283《移动零》

---

第一部分：题目描述

题目名称：移动零 (Move Zeroes)

题目描述

给定一个包含 $n$ 个整数的数组 nums，编写一个程序将该数组中所有的 0 移动到数组的末尾，同时保持非零元素的相对顺序。

注意：

1. 必须在原数组上操作，不能拷贝额外的数组（即空间复杂度要求为 $O(1)$，不计算输出所需的空间）。
2. 尽量减少操作次数。

输入格式

第一行包含一个整数 $n$，表示数组的长度。 第二行包含 $n$ 个整数，表示数组 nums 的元素，相邻整数之间用空格分隔。

输出格式

输出一行，包含 $n$ 个整数，表示移动后的数组，相邻整数之间用空格分隔。

样例数据

Sample Input

5
0 1 0 3 12

Sample Output

1 3 12 0 0

数据范围与提示

• 对于 $60\%$ 的数据，满足 $1 \le n \le 100$。
• 对于 $100\%$ 的数据，满足 $1 \le n \le 10^4$，$-2^{31} \le nums[i] \le 2^{31}-1$。

---

第二部分：教练辅导时间

我是你的教练。拿到这道题，不要急着写代码。我们先来做一下“阅读理解”，然后像在草稿纸上画图一样，把思路推导出来。

1. 读题关键词 (Reading Comprehension)

我们在读题时，要敏锐地捕捉到限制条件，这往往是解题的命门：

• “原地 (In-place)”：这意味着你不能new 一个新数组，也不能定义一个 vector<int> b 然后把非零的放进去。所有的交换、移动都必须在输入的那个数组内存里折腾。这暗示了空间复杂度必须是 $O(1)$。
• “保持非零元素的相对顺序”：这说明不能用不稳定的排序（比如快排的 Partition 思想在这里不能直接乱用），也不能随意交换非零数的位置。例如 [0, 1, 3] 变成 [3, 1, 0] 是错的，必须是 [1, 3, 0]。
• “减少操作次数”：这提示我们要寻找时间复杂度为 $O(n)$ 的算法，最好能一次遍历搞定。

2. 预备知识点

解决这道题，你需要掌握以下基础：

1. 数组的遍历：基本的 for 循环。
2. 双指针技巧 (Two Pointers)：这是本题的核心，特别是“快慢指针”的思想。
3. 交换操作 (Swap)：如何交换两个变量的值（C++中可用 std::swap）。

3. 启发式图解推导 (Heuristic Derivation)

假设我们在教室黑板上，现在有一个数组：[0, 1, 0, 3, 12]。

思路演进过程：

初级想法（暴力法 - 模拟）： 如果不限制空间，我们肯定会开个新数组，先把非0的拷进去，剩下的填0。但题目禁止这样做。 如果在原数组操作，遇到一个0，就把它后面的所有元素往前挪一位，把0放到最后？

• 分析：移动一次数组需要 $O(n)$，如果有 $n$ 个0，总复杂度就是 $O(n^2)$。当 $n=10^4$ 时，操作次数接近 $10^8$，勉强能过，但如果数据强一点就会TLE (Time Limit Exceeded)。我们要追求 $O(n)$。

进阶想法（双指针 - 快慢指针法）：

想象你在整理一排书架，要把所有的书（非0元素）紧凑地移到左边，空位（0）自然就留到了右边。

我们需要两个“手指”（指针）：

• 指针 j (慢指针/由它维护非零序列的尾部)：它指向“当前已经整理好的非零序列”的下一个位置。
• 指针 i (快指针/侦察兵)：它负责在前面探路，寻找非零元素。

草稿纸推演：

初始状态： nums = [0, 1, 0, 3, 12] j = 0 (还没放任何非零数，准备放在下标0) i = 0 (从头开始看)

Step 1: i=0, nums[0] 是 0。

• 既然是0，它是我们要扔到后面的东西，不管它。j 不动（原地待命）。
• i 继续往前走。

Step 2: i=1, nums[1] 是 1 (非0)。

• 找到宝贝了！这个 1 应该放在哪里？应该放在 j 指向的位置（下标0）。
• 操作：把 nums[i] 放到 nums[j]。这里有个技巧：可以直接交换 swap(nums[i], nums[j])。
  • 交换后：nums = [1, 0, 0, 3, 12] (1和0换了位置)
• 既然 j 这个位置已经填好书了，j 向后移一位，准备填下一个。
• j 变为 1。

Step 3: i=2, nums[2] 是 0。

• 又是0，跳过。j 还是 1。

Step 4: i=3, nums[3] 是 3 (非0)。

• 找到宝贝！把 nums[3] 和 nums[j] (也就是 nums[1]) 交换。
  • 交换前：[1, 0, 0, 3, 12] (j在下标1，指向第一个0)
  • 交换后：[1, 3, 0, 0, 12]
• j 向后移一位，j 变为 2。

Step 5: i=4, nums[4] 是 12 (非0)。

• 找到宝贝！把 nums[4] 和 nums[j] (也就是 nums[2]) 交换。
  • 交换前：[1, 3, 0, 0, 12] (j在下标2，指向那个0)
  • 交换后：[1, 3, 12, 0, 0]
• j 向后移一位，j 变为 3。

循环结束。 结果：[1, 3, 12, 0, 0]。完美！

复杂度分析

• 时间复杂度：$i$ 指针从头走到尾，遍历一次，操作都是常数级。复杂度为 $O(n)$。
• 空间复杂度：只用了两个整数变量 $i, j$，没有开数组。复杂度为 $O(1)$。

4. 优化思考

其实还有一种写法： 先把所有非0的数按顺序赋值给 nums[j]，循环结束后，把 j 之后的所有位置手动赋值为 0。

• 比较：赋值法比交换法稍微少几次写操作（因为交换涉及3次读写），但在现代编译器优化下差异极小。交换法（Swap）逻辑上更直观——“把非0数换到前面，0自然就被挤到后面去了”，且能保证不仅非0的相对顺序不变，0之间的相对顺序也不变（虽然题目没要求0的顺序）。

---

第三部分：参考代码 (NOI 标准 C++14)

这是你可以参考的标准写法。但在看代码前，请确保你已经按照上面的“草稿纸推演”自己尝试写了一遍。

/**
 * Title: Moving Zeroes
 * Standard: C++14
 * Note: NOI Style Implementation
 */
#include <iostream>
#include <vector>
#include <algorithm> // for std::swap

// 既然是NOI风格，推荐使用能够加速IO的方法，尽管本题数据量不大
void solve() {
    int n;
    if (!(std::cin >> n)) return;

    // 使用 vector 动态管理，但在比赛中如果 n 确定，也可以开全局数组 int nums[10005]
    std::vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        std::cin >> nums[i];
    }

    // --- 核心算法开始 (Core Logic) ---
    // j 指针指向当前非零元素应该存放的位置
    int j = 0;
    
    // i 指针用于遍历数组
    for (int i = 0; i < n; ++i) {
        // 如果发现非零元素
        if (nums[i] != 0) {
            // 将其交换到 j 的位置
            // 如果 i == j，说明前面没有 0，自己和自己交换（无副作用，或者加个判断跳过）
            // 如果 i > j，说明中间夹了 0，交换会将 0 换到后面去
            std::swap(nums[i], nums[j]);
            j++;
        }
    }
    // --- 核心算法结束 ---

    // 输出结果
    for (int i = 0; i < n; ++i) {
        std::cout << nums[i] << (i == n - 1 ? "" : " ");
    }
    std::cout << std::endl;
}

int main() {
    // 提高 C++ cin/cout 的读写速度，适应大规模数据
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    // 在本地调试时可以使用文件重定向，提交时通常不需要或根据题目要求
    // freopen("move.in", "r", stdin);
    // freopen("move.out", "w", stdout);

    solve();

    return 0;
}

课后总结

这道题是 “数组双指针” 也就是 “快慢指针” 的经典入门题。

• 慢指针 j：维护的是“有效数据的边界”。
• 快指针 i：负责“扫描和筛选”。

记住这个模型，以后遇到“去除数组中的重复项”、“移除指定元素”等题目，思路是一模一样的！