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`` 之后的数组内容都不属于答案,无需清零或恢复。