LeetCode 26. 删除有序数组中的重复项
题目描述
题意分析
对非递减排列的数组原地去重，使每个不同的值只保留一次。返回不同元素个数
k，并把这些值按原顺序放在数组前k个位置。不需要改变数组实际长度，也不用清空后面的内容，只有
[0, k)是有效答案。数组已经有序，相同值必定连续，因此不用集合记录所有出现过的值，只需判断当前值是否与最后一个保留值相同。
解法：快慢指针原地去重
核心思路
[!blue]
用
read按顺序读取原数组，用write指向下一个结果写入位置。始终让[0, write)保存已经读取部分的去重结果，且其中的值按原顺序排列；所以最后一个保留值就是nums[write - 1]。非空数组的第一个元素一定要保留，初始化
write = 1，从下标1开始读取。当前值若等于最后一个保留值，说明仍在同一段重复值中，直接跳过；若不同，由于数组有序，它就是尚未保留的新值，将其写到nums[write]后再增加write。不同值最多与已经读取的元素一样多，因此每次写入前都有
write <= read。写操作只覆盖已读位置或当前正在读取的位置，不会破坏后面尚未处理的数据，这正是能够原地压缩的原因。每轮要么跳过一个重复值，要么把一个新值追加到结果前缀，这个前缀始终正确且完整。扫描结束后，
write既是下一写入位置，也是保留元素的数量，直接返回即可。空数组单独返回0，避免访问第一个元素。
解题步骤
- 数组为空时返回
0；否则保留首元素，令write = 1。- 让
read从下标1扫描到末尾。- 如果
nums[read] == nums[write - 1]，不写入，继续读取下一个位置。- 否则把
nums[read]写入nums[write]，再将write加一。- 返回
write，后缀内容无需处理。
代码实现
class Solution {
public int removeDuplicates(int[] nums) {
if (nums.length == 0) {
return 0;
}
int write = 1;
for (int read = 1; read < nums.length; read++) {
// 与已保留前缀的最后一个值比较，只有新值才写入下一位置。
if (nums[read] != nums[write - 1]) {
nums[write++] = nums[read];
}
}
return write;
}
}
func removeDuplicates(nums []int) int {
if len(nums) == 0 {
return 0
}
write := 1
for read := 1; read < len(nums); read++ {
// 与已保留前缀的最后一个值比较，只有新值才写入下一位置。
if nums[read] != nums[write-1] {
nums[write] = nums[read]
write++
}
}
return write
}
复杂度分析
- 时间复杂度：$O(n)$。读指针只从左到右扫描一遍。
- 空间复杂度：$O(1)$。结果直接写回原数组，只使用常数个变量。
关键点总结
[!green]
- “有序”把全局去重转化为与最后一个保留值比较。
write表示下一个写入位置，也直接等于有效前缀长度，能减少加一减一错误。- 覆盖安全依赖写入前的
write <= read：写操作不会碰到尚未读取的数据。- 题目只校验前
k项，k之后无需清零或截断。
易错点总结
[!yellow]
- 返回
write - 1：write本身就是有效长度，最后一个有效下标才是write - 1。- 只计数不写回：题目同时要求结果前缀正确，发现新值后必须写入下一个有效位置。
- 先增加
write再写入：会跳过一个结果位置，应先写入再推进指针。- 忽略空数组：初始化保留首元素的逻辑只适用于非空数组。
- 额外保存去重集合或清空后缀：前者增加不必要的线性空间，后者也不是返回约定的一部分。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 80. 删除有序数组中的重复项 II | 中等 | 同样用写指针压缩有序数组，原题每个值最多保留两次，本题只保留一次。 |
| 27. 移除元素 | 简单 | 同样稳定写入需保留的元素，原题按指定值筛选，本题按有序相邻重复关系筛选。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！