0026. Remove Duplicates from Sorted Array ========================================= 题目信息 -------- :题号: 0026. 删除有序数组中的重复项 :难度: Easy :主题: 数组、双指针、原地覆盖 :原题: `LeetCode 0026 `_ :重点: 从实际删除重复元素,推导到只维护有效前缀,并用写入位置同时表示不同值数量 题目重述 -------- 给定一个按非递减顺序排列的整数数组 ``nums``,需要在原数组中原地移除重复值,使每个不同数值只保留一次, 并返回不同数值的数量 ``k``。 处理完成后,``nums[0..k-1]`` 必须按原有顺序保存数组中的全部不同值。下标 ``k`` 及其后的内容不参与判定, 可以保留任意值;题目也不要求真正缩短数组容器。算法只能使用常量级额外空间。 数组长度位于 ``[1, 3 * 10^4]``,元素位于 ``[-100, 100]``。由于输入非空,答案 ``k`` 至少为 ``1``。 自建示例 -------- * 多段重复:``nums = [-2, -2, -1, -1, -1, 3, 3, 5]``,返回 ``k = 4``,有效前缀为 ``[-2, -1, 3, 5]``; * 没有重复:``nums = [0, 2, 4, 7]``,返回 ``k = 4``,整个数组都是有效前缀; * 全部相同:``nums = [6, 6, 6, 6]``,返回 ``k = 1``,有效前缀为 ``[6]``; * 重复段位于两端:``nums = [-3, -3, 0, 2, 2]``,返回 ``k = 3``,有效前缀为 ``[-3, 0, 2]``; * 单个元素:``nums = [9]``,返回 ``k = 1``,数组无需改动。 C++ 实现 -------- .. code-block:: cpp #include class Solution { private: int eraseRepeatedValues(std::vector& nums) { int index = 1; while (index < static_cast(nums.size())) { if (nums[index] == nums[index - 1]) { nums.erase(nums.begin() + index); } else { ++index; } } return static_cast(nums.size()); } int copyThroughBuffer(std::vector& nums) { std::vector distinct; distinct.reserve(nums.size()); distinct.push_back(nums[0]); for (int read = 1; read < static_cast(nums.size()); ++read) { if (nums[read] != distinct.back()) { distinct.push_back(nums[read]); } } for (int index = 0; index < static_cast(distinct.size()); ++index) { nums[index] = distinct[index]; } return static_cast(distinct.size()); } int compactInPlace(std::vector& nums) { int write = 1; for (int read = 1; read < static_cast(nums.size()); ++read) { if (nums[read] != nums[write - 1]) { nums[write] = nums[read]; ++write; } } return write; } public: int removeDuplicates(std::vector& nums) { return compactInPlace(nums); } }; 题解 ---- 实际删除 ~~~~~~~~ 最直接的理解是:发现相邻重复值后,就从数组容器中真正删除后一个元素。输入已经有序,相同值必然连续,因此 ``eraseRepeatedValues`` 只需比较 ``nums[index]`` 与 ``nums[index - 1]``。 删除后不能立即增加 ``index``。原来位于 ``index + 1`` 的元素会左移到当前 ``index``,它仍需与前一个保留值 比较。例如 ``[2, 2, 2]`` 删除中间的 ``2`` 后,当前位置仍是另一个 ``2``。 这种方法最终会得到真正缩短且无重复的数组,语义正确,但没有利用题目的判定方式。数组中间执行一次 ``erase`` 需要把后面的所有元素向左搬移;若大量重复值集中在前部,同一批后缀元素可能被反复搬动,最坏时间达到 ``O(n²)``。 题目真正要求的不是缩短容器,而只是构造正确的前 ``k`` 个位置。物理删除完成了不必要的工作。 额外结果数组 ~~~~~~~~~~~~ 为了避免反复搬移,可以顺序扫描输入,把每个新出现的值追加到 ``distinct``。因为数组有序,当前值是否首次出现, 只需与结果中的最后一个值比较。 ``copyThroughBuffer`` 扫描结束后,再把 ``distinct`` 复制回 ``nums`` 的开头。每个输入元素只读取一次,每个不同值 只写入结果数组和原数组各一次,时间降为 ``O(n)``。 这一步已经识别出题目只关心一个连续的无重复结果序列,却仍同时保存了两份内容:原数组和完整的 ``distinct``。既然最终还要把结果写回 ``nums`` 的前缀,就可以直接把原数组前部当作结果缓冲区。 有效前缀 ~~~~~~~~ 原地方法维护 ``write``,它同时具有两种含义: * ``nums[0..write-1]`` 是已经完成的无重复有效前缀; * ``write`` 是下一个新值应写入的位置,也是当前已经保留的不同值数量。 输入非空,第一个元素必然是第一个不同值,因此初始有效前缀为 ``nums[0..0]``,令 ``write = 1``。``read`` 从 下标 ``1`` 开始扫描尚未处理的原始元素。 每轮只需把 ``nums[read]`` 与 ``nums[write - 1]`` 比较: * 两者相等,当前元素仍属于最近一个重复段,直接跳过; * 两者不同,当前元素是下一个尚未保留的新值,把它写入 ``nums[write]``,再增加 ``write``。 这里比较的是“最近保留值”,而不是固定比较某个原始位置。即使前面发生过覆盖,``nums[write - 1]`` 仍精确表示 有效前缀的最后一个不同值。 有序性与重复段 ~~~~~~~~~~~~~~ 非递减顺序保证同一个值只会形成一个连续段。扫描离开某个值段后,后面不可能再次出现该值。 因此,每个值段的第一个元素必然与最近保留值不同,会被写入一次;该段其余元素都与最近保留值相同,会被全部 跳过。算法无需哈希集合记录见过的所有数值,只需保存有效前缀最后一个值。 若输入无序,例如 ``[2, 1, 2]``,第二个 ``2`` 不与最近保留值 ``1`` 相等,却已经出现过;当前方法会错误地 再次保留它。有序条件正是把“是否全局出现过”缩减为“一次相邻边界比较”的依据。 覆盖安全 ~~~~~~~~ 扫描过程中始终有 ``write <= read``: * 初始时二者都为 ``1``; * 跳过重复值时,只有 ``read`` 增加; * 保留新值时,先写入 ``nums[write]``,再让 ``write`` 增加一次,而 ``read`` 也会在本轮结束后增加一次。 所以写入位置只可能是当前位置或当前位置之前,从不会覆盖 ``read + 1`` 及其后的未扫描元素。即使 ``nums[write] = nums[read]`` 发生向前覆盖,未来读取所需的原始后缀仍保持完整。 状态演化 ~~~~~~~~ 以 ``nums = [1, 1, 2, 2, 4, 5]`` 为例: .. list-table:: :header-rows: 1 * - ``read`` - 当前值 - ``write`` - 最近保留值 - 动作 - 有效前缀 * - 1 - 1 - 1 - 1 - 跳过 - ``[1]`` * - 2 - 2 - 1 - 1 - 写入下标 1 - ``[1, 2]`` * - 3 - 2 - 2 - 2 - 跳过 - ``[1, 2]`` * - 4 - 4 - 2 - 2 - 写入下标 2 - ``[1, 2, 4]`` * - 5 - 5 - 3 - 4 - 写入下标 3 - ``[1, 2, 4, 5]`` 扫描结束时 ``write = 4``。原数组可能变为 ``[1, 2, 4, 5, 4, 5]``,后两个位置仍保留旧内容,但题目只检查 前四个位置,因此结果完全符合要求。 循环不变量 ~~~~~~~~~~ 每轮处理 ``nums[read]`` 之前,保持以下状态: * ``nums[0..write-1]`` 按非递减顺序包含已扫描前缀中的全部不同值,每个值恰好一次; * ``nums[read]`` 及其后的元素尚未读取,仍保留扫描所需的原始顺序; * ``write <= read``。 当前值等于最近保留值时,它不会给不同值集合增加新成员,跳过后状态不变。当前值不等时,它是一个新值段的 首元素,写到有效前缀末尾后仍保持有序且不重复。扫描结束时,已扫描前缀就是整个数组,因此有效前缀恰好包含 全部不同值,``write`` 也恰好等于其数量。 代码演进 ~~~~~~~~ ``eraseRepeatedValues`` 在发现重复值时修改数组长度。它得到正确结果,却为每次删除反复搬移后缀。 ``copyThroughBuffer`` 删除了中间 ``erase``,改为只追加新值,时间降为线性;代价是保存一份完整结果数组,随后 还要复制回输入前缀。 ``compactInPlace`` 把额外结果数组替换为 ``nums`` 自身的前缀。``write`` 取代了 ``distinct.size()``, ``nums[write - 1]`` 取代了 ``distinct.back()``,第二次整体复制也随之消失。 公开入口采用 ``compactInPlace``。它直接满足原地修改要求,并让“有效前缀长度”“不同值数量”和“下一写入位置” 统一为同一个变量。 复杂度分析 ~~~~~~~~~~ .. list-table:: :header-rows: 1 * - 方法 - 时间复杂度 - 工作空间 - 主要代价 * - 实际删除 - 最坏 ``O(n²)`` - ``O(1)`` - 每次删除都可能搬移一段数组后缀 * - 额外结果数组 - ``O(n)`` - ``O(n)`` - 保存全部不同值并复制回输入前缀 * - 原地覆盖 - ``O(n)`` - ``O(1)`` - 每个元素读取一次,每个新值至多写入一次 原地方法不会缩短 ``nums``,返回值 ``k`` 用来划定结果前缀。下标 ``k`` 之后的内容属于未指定区域,不计入答案, 也无需额外清理。