0027. Remove Element
====================
题目信息
--------
:题号: 0027. 移除元素
:难度: Easy
:主题: 数组、双指针、原地覆盖
:原题: `LeetCode 0027 `_
:重点: 从实际删除元素,推导到维护有效前缀,并比较稳定覆盖与尾部替换的写入代价
题目重述
--------
给定整数数组 ``nums`` 和整数 ``val``,原地移除所有等于 ``val`` 的元素,并返回未被移除的元素数量 ``k``。
处理完成后,``nums`` 的前 ``k`` 个位置必须包含原数组中全部不等于 ``val`` 的元素,每个保留元素出现的次数不变。
这些元素的相对顺序可以改变;下标 ``k`` 及其后的内容不作要求。题目要求只使用 ``O(1)`` 额外空间,不能另建
完整结果数组代替原数组。
``nums`` 的长度位于 ``[0, 100]``,数组元素位于 ``[0, 50]``,``val`` 位于 ``[0, 100]``。
自建示例
--------
* 多次出现:``nums = [3, 1, 3, 2, 4, 3]``、``val = 3``,返回 ``k = 3``;有效前缀可以是
``[1, 2, 4]``,也可以是包含相同三个值的其他顺序;
* 目标值不存在:``nums = [0, 2, 5]``、``val = 7``,返回 ``k = 3``,全部元素都保留;
* 全部移除:``nums = [4, 4, 4]``、``val = 4``,返回 ``k = 0``;
* 空数组:``nums = []``、``val = 1``,返回 ``k = 0``;
* 只移除首尾:``nums = [6, 1, 2, 6]``、``val = 6``,返回 ``k = 2``,有效前缀包含 ``1`` 和 ``2``。
C++ 实现
--------
.. code-block:: cpp
#include
class Solution {
private:
int eraseMatches(std::vector& nums, int val) {
for (int index = 0; index < static_cast(nums.size());) {
if (nums[index] == val) {
nums.erase(nums.begin() + index);
} else {
++index;
}
}
return static_cast(nums.size());
}
int stableCompaction(std::vector& nums, int val) {
int write = 0;
for (int read = 0; read < static_cast(nums.size()); ++read) {
if (nums[read] != val) {
nums[write] = nums[read];
++write;
}
}
return write;
}
int replaceFromEnd(std::vector& nums, int val) {
int index = 0;
int activeSize = static_cast(nums.size());
while (index < activeSize) {
if (nums[index] == val) {
--activeSize;
nums[index] = nums[activeSize];
} else {
++index;
}
}
return activeSize;
}
public:
int removeElement(std::vector& nums, int val) {
return stableCompaction(nums, val);
}
};
题解
----
实际删除
~~~~~~~~
最直接的理解是:扫描数组,遇到 ``val`` 就调用 ``erase``,让容器真正删除该位置。``eraseMatches`` 按照这个定义
执行,循环结束后数组中只剩保留元素,返回的新长度就是答案。
删除后不能立即增加 ``index``。原下一个元素已经左移到当前下标,尚未检查;若直接前进,连续目标值中的第二个就会
被跳过。
这个方法语义正确,问题出在数组中间删除的代价。删除一个位置后,其后的全部元素都要左移一格。若长度为 ``n``
的数组中存在大量待删除元素,同一批后缀可能被反复搬移,最坏时间达到 ``O(n²)``。
有效前缀
~~~~~~~~
题目并不要求缩短 ``nums``,也不关心答案前缀之后的内容。真正需要完成的只有两件事:
* 计算有多少个元素不等于 ``val``;
* 把这些元素放入数组开头连续的 ``k`` 个位置。
因此不必在每次命中时维持整个数组都有效。可以把数组分成“已经完成的有效前缀”和“尚未扫描的区域”,用覆盖代替
物理删除。删除引起的反复后缀搬移由一次顺序扫描取代。
稳定覆盖
~~~~~~~~
``stableCompaction`` 使用两个位置:
* ``read`` 指向当前检查的原元素;
* ``write`` 指向下一个保留元素应写入的位置。
处理 ``read`` 之前,``nums[0..write)`` 恰好包含已扫描前缀中所有不等于 ``val`` 的元素,并保持原相对顺序。
若 ``nums[read] == val``,当前元素不属于答案,``write`` 不变;若不相等,就把它写入 ``nums[write]``,再增加
``write``。两种操作都使有效前缀继续精确对应已扫描区域中的保留元素。
状态演化
~~~~~~~~
以 ``nums = [3, 1, 3, 2, 4, 3]``、``val = 3`` 为例:
.. list-table::
:header-rows: 1
* - ``read``
- 当前值
- 动作
- 新 ``write``
- 有效前缀
* - 0
- 3
- 跳过
- 0
- 空
* - 1
- 1
- 写入下标 0
- 1
- ``[1]``
* - 2
- 3
- 跳过
- 1
- ``[1]``
* - 3
- 2
- 写入下标 1
- 2
- ``[1, 2]``
* - 4
- 4
- 写入下标 2
- 3
- ``[1, 2, 4]``
* - 5
- 3
- 跳过
- 3
- ``[1, 2, 4]``
扫描结束时,``write`` 既是保留元素数量,也是有效前缀长度,因此可以直接返回。
覆盖安全
~~~~~~~~
``write`` 只在发现保留元素时增加,而 ``read`` 每轮都会增加,所以处理任意位置时始终满足
``write <= read``。
写入只可能发生在当前读取位置或它之前,不会覆盖 ``read + 1`` 之后尚未扫描的元素。即使 ``write == read``,
赋值也只是把元素写回原位置。原数组因此可以同时承担输入和输出缓冲区,不需要额外结果数组。
尾部替换
~~~~~~~~
题目明确允许改变保留元素顺序,这又产生另一条优化路线。若当前位置等于 ``val``,可以用当前活动区间的最后一个
元素覆盖它,再把活动区间长度减一:
.. code-block:: text
[已确认保留 | 当前检查 | 尚未检查 ........ | 活动末尾] [无效区域]
``replaceFromEnd`` 使用 ``[index, activeSize)`` 表示仍待处理的活动区域。命中目标值时,先执行
``--activeSize``,再把新的末尾元素复制到 ``index``。被覆盖进来的元素原来位于尚未检查区域,它可能仍等于
``val``,所以本轮不能增加 ``index``,下一轮必须继续检查同一位置。
若当前值不等于 ``val``,它已经处于最终有效前缀中,才可以增加 ``index``。循环结束时
``index == activeSize``,前缀 ``nums[0..activeSize)`` 中没有目标值,后面的区域不再属于答案。
两种线性方法的取舍
~~~~~~~~~~~~~~~~~~
稳定覆盖与尾部替换都把时间降为 ``O(n)``,但利用的题意不同:
* 稳定覆盖按原顺序读取和写入,保留元素的相对顺序不变;
* 尾部替换利用“顺序不限”,用未检查的末尾元素填补目标位置。
设最终保留 ``k`` 个元素,删除 ``r = n - k`` 个元素。当前代码中,稳定覆盖对每个保留元素写一次,约有 ``k``
次写入;尾部替换每缩短一次活动区间写一次,约有 ``r`` 次写入。因此尾部替换通常在待删除元素较少时更有优势,
而不是在目标值很多时更有优势。
例如数组中没有 ``val`` 时,尾部替换不执行任何写入,稳定覆盖会把每个元素写回原位置;全部元素都等于
``val`` 时,稳定覆盖不写入任何元素,尾部替换则会连续缩短活动区间。
公开入口采用 ``stableCompaction``。它同样满足原地和线性时间要求,同时保持输入中保留元素的相对顺序,状态定义
更直接。尾部替换适合顺序完全无关且希望在删除项稀少时减少写入的场景。
代码演进
~~~~~~~~
``eraseMatches`` 在每次命中时维护整个数组的连续性,因此一个删除动作会反复搬移尚未处理的长后缀。
``stableCompaction`` 不再真正缩短容器,只维护有效前缀。``erase``、动态数组长度变化和重复后缀移动全部消失,
代码只剩一次读取、条件筛选和必要写入。
``replaceFromEnd`` 从同一个“只要求有效前缀”的认识分叉。它进一步利用结果顺序不限,不再搬运删除位置之后的全部
保留元素,而是用活动末尾一次填补当前空位;代价是失去稳定顺序,并且覆盖后必须重新检查当前下标。
复杂度分析
~~~~~~~~~~
.. list-table::
:header-rows: 1
* - 方法
- 时间复杂度
- 工作空间
- 顺序
- 主要代价
* - 逐个物理删除
- ``O(n²)``
- ``O(1)``
- 保持
- 每次删除都可能搬移整个后缀
* - 稳定覆盖
- ``O(n)``
- ``O(1)``
- 保持
- 每个元素读取一次,保留元素写入前缀
* - 尾部替换
- ``O(n)``
- ``O(1)``
- 改变
- 每轮增加左边界或缩短活动区间
尾部替换中,``index`` 最多增加 ``n`` 次,``activeSize`` 最多减少 ``n`` 次,所以循环总次数仍为线性数量级。
三种方法返回的 ``k`` 之后的数组内容都不属于答案,无需清零或恢复。