LeetCode 26. 删除有序数组中的重复项

约 5 分钟
文章信息 22 个分类 4 个标签
分类
LeetCode CodeTop 简单 已解决 已掌握 20-50 字节跳动 微软 美团 阿里巴巴 快手 腾讯 猿辅导 百度 京东 拼多多 网易 小米 商汤 虾皮 图森 面试经典 150 题
标签
数组 双指针 双指针经典题 元素去重问题
目录

题目描述

✅ 26. 删除有序数组中的重复项

image-20230309214358517

题意分析

给定一个「非递减」排列的整数数组 nums，要求原地删掉重复出现的元素，让每个不同的值只保留一次，最后返回去重后的元素个数 k。

题面里最关键的信号是「已排序」。排序意味着相等的元素必然挨在一起，判断一个值是不是「新值」，只需要和上一个保留下来的值比一次，而不需要回头查它在前面有没有出现过。这条约束把「集合去重」降级成了「相邻比较」。

第二个信号是「原地」加「返回长度」。判题只看 nums 的前 k 个位置是否等于期望的去重结果，第 k 个位置往后的内容是什么完全不作数。所以不需要把尾巴清空，也不允许另开一个数组再拷回来。

边界上要留意三处：数组为空时答案是 0；数组只有一个元素时答案是 1；数组全是同一个值时答案也是 1，写回操作一次都不会发生。这三种情况都必须落在同一套逻辑里，不能靠特判堆出来。

解法：快慢指针原地去重

核心思路

问题关键：数组已经有序，相同元素必然连续；题目只要求前 k 个位置有效，后面的内容无需处理。因此不需要哈希表，也不需要真的删除元素，只要把每段重复值的第一个写到数组前部。

为什么选择快慢指针：read 负责读取原数组，write 指向下一个结果写入位置。新值出现时写入并推进 write，重复值直接跳过。每次执行写入前都有 write <= read，所以覆盖的只会是已经读过的位置，不会破坏未扫描数据。

不变量：每轮开始时，nums[0..write) 恰好是 nums[0..read) 去重后的有序结果，write 同时也是当前不同元素的个数。因为结果区非空时最后一个保留值是 nums[write - 1]，当前值只需与它比较。

正确性：若 nums[read] == nums[write - 1]，它与最近保留值属于同一重复段，跳过后结果不变；若不等，由于数组有序，它一定是尚未出现的新值，将它写到 nums[write] 后结果仍有序且无重复。循环结束时 read == n，由不变量可知前 write 项就是整个数组的去重结果。

解题步骤

  1. 空数组返回 0；否则首元素必然保留，初始化 write = 1。
  2. 让 read 从 1 扫描到数组末尾。
  3. 若 nums[read] 等于 nums[write - 1]，说明重复，继续扫描。
  4. 否则把当前值写入 nums[write]，再令 write++。
  5. 扫描结束后返回 write。

例如 [0,0,1,1,2]：初始结果区为 [0]；第二个 0 被跳过，1 写到下标 1，第二个 1 被跳过，2 写到下标 2。最终前缀是 [0,1,2]，返回 3。

代码实现

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)$。结果直接写回原数组，只使用常数个变量。

关键点总结

  • “有序”把全局去重转化为与最后一个保留值比较。
  • write 表示下一个写入位置，也直接等于有效前缀长度，能减少加一减一错误。
  • 覆盖安全依赖写入前的 write <= read：写操作不会碰到尚未读取的数据。
  • 题目只校验前 k 项，k 之后无需清零或截断。

易错点总结

  • 返回 write - 1：write 是长度而非最后一个下标；[1,1,2] 应返回 2。
  • 与 nums[read - 1] 比较后不写回：虽然能识别新值，但 [0,0,1] 的前两项仍是 [0,0]，没有形成有效结果前缀。
  • 先移动 write 再写入：会跳过一个结果位置，甚至在全不重复时越界；本写法应先写 nums[write]，再自增。
  • 忘记处理空数组：初始化 write = 1 后会错误返回 1。即使题库约束非空，面试中也应先确认输入约束。
  • 使用哈希集合：答案可以算对，但浪费 $O(n)$ 空间，也没有利用已排序条件，不符合原地要求。

相似题目

题目 难度 考察点
27. 移除元素 简单 判重条件换成与给定目标值比较，无需数组有序
80. 删除有序数组中的重复项 II 中等 每个值允许保留两次，比较对象后移到 nums[slow - 2]
283. 移动零 简单 保留区之外还要求把零补到尾部，需交换而非覆盖
443. 压缩字符串 中等 写指针要回填连续段的计数字符，写入长度不固定