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`` 之后的内容属于未指定区域,不计入答案,
也无需额外清理。