0026. Remove Duplicates from Sorted Array¶
题目信息¶
- 题号:
删除有序数组中的重复项
- 难度:
Easy
- 主题:
数组、双指针、原地覆盖
- 原题:
- 重点:
从实际删除重复元素,推导到只维护有效前缀,并用写入位置同时表示不同值数量
题目重述¶
给定一个按非递减顺序排列的整数数组 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++ 实现¶
#include <vector>
class Solution {
private:
int eraseRepeatedValues(std::vector<int>& nums) {
int index = 1;
while (index < static_cast<int>(nums.size())) {
if (nums[index] == nums[index - 1]) {
nums.erase(nums.begin() + index);
} else {
++index;
}
}
return static_cast<int>(nums.size());
}
int copyThroughBuffer(std::vector<int>& nums) {
std::vector<int> distinct;
distinct.reserve(nums.size());
distinct.push_back(nums[0]);
for (int read = 1; read < static_cast<int>(nums.size()); ++read) {
if (nums[read] != distinct.back()) {
distinct.push_back(nums[read]);
}
}
for (int index = 0; index < static_cast<int>(distinct.size()); ++index) {
nums[index] = distinct[index];
}
return static_cast<int>(distinct.size());
}
int compactInPlace(std::vector<int>& nums) {
int write = 1;
for (int read = 1; read < static_cast<int>(nums.size()); ++read) {
if (nums[read] != nums[write - 1]) {
nums[write] = nums[read];
++write;
}
}
return write;
}
public:
int removeDuplicates(std::vector<int>& 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] 为例:
|
当前值 |
|
最近保留值 |
动作 |
有效前缀 |
|---|---|---|---|---|---|
1 |
1 |
1 |
1 |
跳过 |
|
2 |
2 |
1 |
1 |
写入下标 1 |
|
3 |
2 |
2 |
2 |
跳过 |
|
4 |
4 |
2 |
2 |
写入下标 2 |
|
5 |
5 |
3 |
4 |
写入下标 3 |
|
扫描结束时 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。它直接满足原地修改要求,并让“有效前缀长度”“不同值数量”和“下一写入位置”
统一为同一个变量。
复杂度分析¶
方法 |
时间复杂度 |
工作空间 |
主要代价 |
|---|---|---|---|
实际删除 |
最坏 |
|
每次删除都可能搬移一段数组后缀 |
额外结果数组 |
|
|
保存全部不同值并复制回输入前缀 |
原地覆盖 |
|
|
每个元素读取一次,每个新值至多写入一次 |
原地方法不会缩短 nums,返回值 k 用来划定结果前缀。下标 k 之后的内容属于未指定区域,不计入答案,
也无需额外清理。