第一部分：题目描述

题目名称： 数组元素的就地移除 (Remove Element In-Place) 输入文件： remove.in 输出文件： remove.out 时间限制： 1.0 s 空间限制： 256 MB

【题目描述】

给定一个长度为 $n$ 的整数数组 nums 和一个整数 val。你需要原地 (In-Place) 移除数组中所有数值等于 val 的元素。

“原地”修改是指：你不能使用额外的数组空间（即空间复杂度必须为 $O(1)$），必须直接修改输入数组 nums。 移除后，数组中剩余元素的相对顺序可以改变（本题不强制要求保持相对顺序，但通常保持顺序的做法最通用）。

你需要完成以下两件事：

1. 计算移除 val 后，数组中剩余元素的数量 k。
2. 将剩余的 k 个元素存放在数组 nums 的前 k 个位置（索引 $0$ 到 $k-1$）。

注意：数组 nums 中超出前 k 个元素的部分（即索引 $k$ 及之后的位置）可以是任意值，评测系统不予关心。

【输入格式】

输入文件包含三行： 第一行包含一个整数 $n$，表示数组 nums 的长度。 第二行包含 $n$ 个整数，表示数组 nums 的元素，整数之间用空格分隔。 第三行包含一个整数 val，表示需要移除的目标值。

【输出格式】

输出文件包含两行： 第一行输出一个整数 k，表示移除后数组的新长度。 第二行输出 k 个整数，表示修改后的数组的前 k 个元素。如果 k=0，则此行为空。

【输入样例 1】

4
3 2 2 3
3

【输出样例 1】

2
2 2

(说明：原数组为 [3,2,2,3]，val=3。移除3后，剩余两个元素均为2。长度为2。)

【输入样例 2】

8
0 1 2 2 3 0 4 2
2

【输出样例 2】

5
0 1 3 0 4

(说明：移除了所有的2，剩余5个元素。注意：只要前5个元素包含0,1,3,0,4即可，顺序不严格限制，但通常解法会保持顺序)

【数据范围与提示】

• $0 \le n \le 100$
• $0 \le nums[i] \le 50$
• $0 \le val \le 100$
• 注意： 评测机在检查时，首先读取你输出的长度 k，然后会检查你输出的数组前 k 个元素是否均不等于 val，且包含了原数组中所有不等于 val 的数字。

---

第二部分：教练辅导时间

1. 思路提示 (Hint)

• 思考点 1： 题目强调了“原地 (In-Place)”。这意味着你不能写 int b[105] 然后把好的数字存进去。你只能在 nums 数组这一块内存上操作。
• 思考点 2： 如果你发现一个数字是“坏的”（等于 val），你需要删掉它。在数组中删掉一个元素通常意味着把后面的元素往前挪，或者用别的元素覆盖它。
• 思考点 3： 想象你在整理一排书，要把所有不需要的书（val）扔掉，需要的书留下来并排在最前面。你可以用两只手指（两个变量）来辅助你工作：一只手指负责“寻找”好书，另一只手指负责“指示”好书应该放的位置。

2. 预备知识点 (Prerequisites)

• 数组 (Array) 的基本操作：下标访问、遍历。
• 双指针算法 (Two Pointers)：特别是“快慢指针”技巧。
  • 快指针（Fast Pointer）：用于遍历数组，寻找我们需要的元素。
  • 慢指针（Slow Pointer）：指向下一个存放“有效元素”的位置。
• 变量自增：理解 nums[k++] = val 和 nums[k] = val; k++; 的等价性。

3. 启发式教学与草稿纸推演 (Heuristic Approach)

来，拿出草稿纸，我们画图模拟一下快慢指针的过程。

场景设置：

• 数组 nums = [0, 1, 2, 2, 3, 0, 4, 2]
• 目标 val = 2 (我们要消灭所有的 2)

变量定义：

• i (快指针)：用来扫描每一个数字，问“你是2吗？”
• k (慢指针)：代表“当前有效数组的尾部”，或者说“下一个好数字应该放的位置”。初始为 0。

推演步骤：

步骤	快指针 i 的值	nums[i] 的值	是否等于 val?	操作	慢指针 k 的状态	数组当前样子 (前k位)
Start	0		否 (好数)	把 nums[i] 抄到 nums[k] nums[0] = 0 k 变为 1	k=1	[0, ...]
Step 1	1			把 nums[i] 抄到 nums[k] nums[1] = 1 k 变为 2	k=2	[0, 1, ...]
Step 2	2	2	是 (坏数)	跳过！ 既然是坏数，不要放到 k 的位置。 k 保持不变。		[0, 1, ...] (没变)
Step 3	3			跳过！ k 保持不变。
Step 4	4	3	否 (好数)	nums[k] = nums[i] 即 nums[2] = 3 k 变为 3	k=3	[0, 1, 3, ...]
...	...

图形化思考：

你可以把 k 想象成一道闸门。

• i 在前面跑，遇到非 val 的数，就扔给 k，k 把这个数砌到墙里，然后闸门往后移一格。
• 遇到 val，i 直接无视，继续跑，k 待在原地不动。

复杂度分析：

• 时间复杂度： 看看 i 走了多远？从 $0$ 走到 $n-1$。只遍历了一次。所以是 $O(N)$。
• 空间复杂度： 我们只用了 i, k, n, val 这几个变量，没有开新数组。所以是 $O(1)$。

优化思考： 题目提到“元素的顺序可以改变”。

• 如果数组是 [1, 2, 3, 4, 5, 2], val = 2。
• 如果用上面的方法，需要把 3, 4, 5 都往前挪。
• 进阶思路（针对极少需要移除的情况）： 如果我们要移除的元素很少，能否把最后一个元素直接搬过来覆盖掉当前的 val？这叫做“对撞指针”或“交换移除”，可以减少赋值操作的次数，但会打乱顺序。对于NOI初学者，掌握快慢指针（保序）是第一优先级。

4. 读题关键词总结 (Key Terms)

在做此类题目时，请圈出以下关键词：

1. “原地” (In-place) -> 禁止 new array，必须操作原数组下标。
2. “不需要考虑数组中超出新长度后面的元素” -> 说明我们只需要保证前 k 个是对的，不用手动去清空或把后面的部分变成0。
3. “返回新的长度” -> 输出不仅是数组，还有一个整数计数器。

---

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

/**
 * 题目：移除元素 (Remove Element)
 * 来源：改编自 LeetCode 27
 * 语言：C++14
 * 风格：NOI/CSP 竞赛标准风格
 */

#include <iostream>
#include <vector>

using namespace std;

// 核心逻辑函数：模拟提交给LeetCode的部分
// 在竞赛中，通常这部分逻辑会直接写在 main 函数里，
// 但为了养成模块化思维，我们将其封装。
int removeElement(vector<int>& nums, int val) {
    int n = nums.size();
    int k = 0; // 慢指针：指向下一个存放“非val”元素的位置

    for (int i = 0; i < n; ++i) { // 快指针 i：遍历数组
        if (nums[i] != val) {
            nums[k] = nums[i]; // 将有效元素复制到慢指针位置
            k++;               // 慢指针向前移动
        }
        // 如果 nums[i] == val，则不做任何操作，快指针 i 继续向后找
    }
    return k; // 返回新数组的长度
}

int main() {
    // 提高 I/O 效率，竞赛常用
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    // 1. 读取输入 n
    int n;
    if (!(cin >> n)) return 0;

    // 2. 读取数组
    vector<int> nums(n);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }

    // 3. 读取 val
    int val;
    cin >> val;

    // 4. 执行算法
    int newLength = removeElement(nums, val);

    // 5. 按照格式输出
    cout << newLength << endl;
    for (int i = 0; i < newLength; ++i) {
        cout << nums[i] << (i == newLength - 1 ? "" : " ");
    }
    cout << endl;

    return 0;
}

希望这份辅导材料能帮助你掌握“原地移除元素”的核心思想！如果有哪一步推演不清楚，请随时在草稿纸上再画一遍流程。加油！