0027. Remove Element

题目信息

题号:
  1. 移除元素

难度:

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++ 实现

#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 为例:

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,可以用当前活动区间的最后一个 元素覆盖它,再把活动区间长度减一:

[已确认保留 | 当前检查 | 尚未检查 ........ | 活动末尾] [无效区域]

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 从同一个“只要求有效前缀”的认识分叉。它进一步利用结果顺序不限,不再搬运删除位置之后的全部 保留元素,而是用活动末尾一次填补当前空位;代价是失去稳定顺序,并且覆盖后必须重新检查当前下标。

复杂度分析

方法

时间复杂度

工作空间

顺序

主要代价

逐个物理删除

O(n²)

O(1)

保持

每次删除都可能搬移整个后缀

稳定覆盖

O(n)

O(1)

保持

每个元素读取一次,保留元素写入前缀

尾部替换

O(n)

O(1)

改变

每轮增加左边界或缩短活动区间

尾部替换中,index 最多增加 n 次,activeSize 最多减少 n 次,所以循环总次数仍为线性数量级。 三种方法返回的 k 之后的数组内容都不属于答案,无需清零或恢复。