LC27. 移除元素

题目描述

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。 不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。

说明: 为什么返回数值是整数，但输出的答案是数组呢? 请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。 你可以想象内部操作如下: // nums 是以“引用”方式传递的。也就是说，不对实参作任何拷贝 int len = removeElement(nums, val);

// 在函数里修改输入数组对于调用者是可见的。 // 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。 for (int i = 0; i < len; i++) { print(nums[i]); }

示例 1： 输入：nums = [3,2,2,3], val = 3 输出：2, nums = [2,2] 解释：函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。你不需要考虑数组中超出新长度后面的元素。例如，函数返回的新长度为 2 ，而 nums = [2,2,3,3] 或 nums = [2,2,0,0]，也会被视作正确答案。 示例 2： 输入：nums = [0,1,2,2,3,0,4,2], val = 2 输出：5, nums = [0,1,4,0,3] 解释：函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。注意这五个元素可为任意顺序。你不需要考虑数组中超出新长度后面的元素。

提示： 0 <= nums.length <= 100 0 <= nums[i] <= 50 0 <= val <= 100

题目解析

题目在说什么

这道题给你一个数组（比如 [3,2,2,3]）和一个目标值（比如 3），你要做的是：把数组里所有等于这个目标值的元素删掉，然后返回删除后数组还剩多少个元素。

注意几个关键点：

• 必须原地修改数组，不能新建一个数组来存结果。
• 返回的是新数组的长度（整数），但调用者会通过这个长度去打印数组的前几个元素，所以数组的前面部分必须放的是剩下的元素。
• 剩下的元素顺序可以任意，不用保持原来的顺序。
• 数组后面多出来的位置（超出新长度的部分）可以不管，里面是什么都行。

举个例子： nums = [3,2,2,3]，val = 3 把所有的 3 删掉后，剩下 [2,2]，长度是 2。 那么数组的前两个位置必须是 2 和 2，后面两个位置可以是任何数（比如 [2,2,3,3] 或 [2,2,0,0] 都算对）。

---

思路是怎么来的

想象你有一个装满玩具的盒子，里面有一些你不想要的玩具（等于 val 的那些）。你想把这些不想要的玩具扔掉，但你不能换一个新盒子，只能在这个旧盒子里操作。

一个很自然的想法是：把不想要的玩具移到盒子的一边，然后把它们一起扔掉。

具体怎么做呢？你可以用两个“指针”来帮忙：

• 一个指针（叫 left）从左边开始，它指向的位置是“存放好玩具”的地方。
• 另一个指针（叫 right）从右边开始，它指向的位置是“还没检查的玩具”。

过程就像这样： 1. 如果 right 指向的玩具是你想要的（不等于 val），就把它放到 left 的位置，然后 left 向右移动一位，right 也向右移动一位。 2. 如果 right 指向的玩具是你不想要的（等于 val），那就直接跳过它，right 向右移动一位，left 不动。 3. 重复直到 right 走完整个盒子。

这样，left 左边（包括 left 本身）的所有玩具都是你想要的，而 left 右边的玩具都是你不想要的。最后返回 left 的值，就是想要的玩具的数量。

这个思路的关键是：用两个指针，一个负责“收集”想要的元素，一个负责“扫描”所有元素。这样只需要遍历一次数组，而且不需要额外空间。

---

代码逐步拆解

我们来看一个常见的解法（双指针法）：

def removeElement(nums, val):
    left = 0  # 慢指针，指向下一个要放“好元素”的位置
    for right in range(len(nums)):  # 快指针，遍历整个数组
        if nums[right] != val:  # 如果当前元素不是要删除的
            nums[left] = nums[right]  # 把它放到 left 的位置
            left += 1  # left 向右移动，准备放下一个
    return left  # left 就是新数组的长度

逐步拆解：

1. 初始化 `left = 0` left 是一个“慢指针”，它指向的位置是下一个要存放“好元素”的地方。一开始，第一个好元素应该放在索引 0 的位置。

2. `for right in range(len(nums))` right 是一个“快指针”，它会从数组的第一个元素走到最后一个元素，检查每一个元素。

3. `if nums[right] != val:` 如果当前元素不是我们要删除的（即不等于 val），说明它是“好元素”，需要保留。

4. `nums[left] = nums[right]` 把这个好元素复制到 left 指向的位置。注意：如果 left 和 right 指向同一个位置（比如一开始），这个赋值相当于没变，但没关系。

5. `left += 1` 把 left 向右移动一位，准备接收下一个好元素。