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

LC26. 删除有序数组中的重复项 视频地址：删除有序数组中的重复项(LeetCode 26)

题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。 将最终结果插入 nums 的前 k 个位置后返回 k 。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 判题标准: 系统会用下面的代码来测试你的题解: int[] nums = [...]; // 输入数组 int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length; for (int i = 0; i < k; i++) { assert nums[i] == expectedNums[i]; } 如果所有断言都通过，那么您的题解将被 通过。 示例 1： 输入：nums = [1,1,2] 输出：2, nums = [1,2,_] 解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。 示例 2： 输入：nums = [0,0,1,1,1,2,2,3,3,4] 输出：5, nums = [0,1,2,3,4] 解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。 提示： 1 <= nums.length <= 3 * 10^4 -10^4 <= nums[i] <= 10^4 nums 已按 升序 排列

题目解析

解题思路

题目要求原地删除有序数组中的重复项，且只能使用 O(1) 额外空间。由于数组已升序排列，重复元素必然相邻，因此可以用双指针技巧：一个指针 i 遍历原数组，另一个指针 j 指向当前不重复序列的末尾位置（即下一个待覆盖的位置）。当遇到新元素（第一个元素或与前一个不同的元素）时，将其复制到 j 位置，然后 j 后移一位。最终 j 的值就是去重后数组的长度。

关键步骤

1. 初始化 j = 0，表示当前不重复序列的写入位置。 2. 遍历数组 i 从 0 到 n-1：

• 若 i == 0（第一个元素必保留）或 nums[i] != nums[i-1]（发现新元素），则执行：
• nums[j] = nums[i]（将新元素写入 j 位置）
• j += 1（更新写入位置）

3. 返回 j 作为新长度。

示意图（以 [0,0,1,1,2] 为例）：

初始: nums = [0, 0, 1, 1, 2], j=0
i=0: 第一个元素, 写入 nums[0]=0, j=1
i=1: nums[1]==nums[0], 跳过
i=2: nums[2]!=nums[1], 写入 nums[1]=1, j=2
i=3: nums[3]==nums[2], 跳过
i=4: nums[4]!=nums[3], 写入 nums[2]=2, j=3
结果: nums前3位为 [0,1,2], 返回 j=3

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组长度，只需一次线性遍历。
• 空间复杂度：O(1)，只使用了两个指针变量，没有额外数组空间。