0027. Remove Element¶
题目信息¶
- 题号:
移除元素
- 难度:
Easy
- 主题:
数组、双指针、原地覆盖
- 原题:
- 重点:
从实际删除元素,推导到维护有效前缀,并比较稳定覆盖与尾部替换的写入代价
题目重述¶
给定整数数组 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++ 实现¶
#include <vector>
class Solution {
private:
int eraseMatches(std::vector<int>& nums, int val) {
for (int index = 0; index < static_cast<int>(nums.size());) {
if (nums[index] == val) {
nums.erase(nums.begin() + index);
} else {
++index;
}
}
return static_cast<int>(nums.size());
}
int stableCompaction(std::vector<int>& nums, int val) {
int write = 0;
for (int read = 0; read < static_cast<int>(nums.size()); ++read) {
if (nums[read] != val) {
nums[write] = nums[read];
++write;
}
}
return write;
}
int replaceFromEnd(std::vector<int>& nums, int val) {
int index = 0;
int activeSize = static_cast<int>(nums.size());
while (index < activeSize) {
if (nums[index] == val) {
--activeSize;
nums[index] = nums[activeSize];
} else {
++index;
}
}
return activeSize;
}
public:
int removeElement(std::vector<int>& 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 为例:
|
当前值 |
动作 |
新 |
有效前缀 |
|---|---|---|---|---|
0 |
3 |
跳过 |
0 |
空 |
1 |
1 |
写入下标 0 |
1 |
|
2 |
3 |
跳过 |
1 |
|
3 |
2 |
写入下标 1 |
2 |
|
4 |
4 |
写入下标 2 |
3 |
|
5 |
3 |
跳过 |
3 |
|
扫描结束时,write 既是保留元素数量,也是有效前缀长度,因此可以直接返回。
覆盖安全¶
write 只在发现保留元素时增加,而 read 每轮都会增加,所以处理任意位置时始终满足
write <= read。
写入只可能发生在当前读取位置或它之前,不会覆盖 read + 1 之后尚未扫描的元素。即使 write == read,
赋值也只是把元素写回原位置。原数组因此可以同时承担输入和输出缓冲区,不需要额外结果数组。
尾部替换¶
题目明确允许改变保留元素顺序,这又产生另一条优化路线。若当前位置等于 val,可以用当前活动区间的最后一个
元素覆盖它,再把活动区间长度减一:
[已确认保留 | 当前检查 | 尚未检查 ........ | 活动末尾] [无效区域]
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 从同一个“只要求有效前缀”的认识分叉。它进一步利用结果顺序不限,不再搬运删除位置之后的全部
保留元素,而是用活动末尾一次填补当前空位;代价是失去稳定顺序,并且覆盖后必须重新检查当前下标。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
顺序 |
主要代价 |
|---|---|---|---|---|
逐个物理删除 |
|
|
保持 |
每次删除都可能搬移整个后缀 |
稳定覆盖 |
|
|
保持 |
每个元素读取一次,保留元素写入前缀 |
尾部替换 |
|
|
改变 |
每轮增加左边界或缩短活动区间 |
尾部替换中,index 最多增加 n 次,activeSize 最多减少 n 次,所以循环总次数仍为线性数量级。
三种方法返回的 k 之后的数组内容都不属于答案,无需清零或恢复。