当前位置：首页 > news >正文

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

news 2025/3/17 18:50:48

一、问题描述

二、解题思路

三、代码

四、复杂度分析

一、问题描述

给你一个 非严格递增排列 的数组 nums ，请你原地删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持一致。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案int k = removeDuplicates(nums); // 调用assert k == expectedNums.length;
for (int i = 0; i < k; i++) {assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被通过。

二、解题思路

初始化指针：
- 使用一个指针 i 指向当前唯一元素的最后位置，初始时为 0，因为第一个元素一定是唯一的。
- 使用另一个指针 j 遍历数组，检查每一个元素是否是新元素。
遍历数组：
- 从数组的第二个元素（j = 1）开始，比较它和前一个元素（即 nums[j] 与 nums[i]）。
- 如果 nums[j] != nums[i]，说明这是一个新的元素，应该将 nums[j] 移动到数组的下一个唯一位置，即 nums[i + 1]，然后将 i 加 1。
结束条件：
- 当遍历完整个数组时，指针 i + 1 就是唯一元素的个数 k，并且前 k 个位置已经被修改为唯一元素。

三、代码

class Solution {public int removeDuplicates(int[] nums) {// 如果数组为空或者只有一个元素，则直接返回该数组的长度if (nums.length == 0) return 0;// 初始化指针 i 指向唯一元素的位置int i = 0;// 遍历数组，j 从 1 开始，因为第一个元素一定是唯一的for (int j = 1; j < nums.length; j++) {// 如果找到一个新元素（和上一个唯一元素不同）if (nums[j] != nums[i]) {// 更新唯一元素的下一个位置，保存新元素i++;nums[i] = nums[j];}}// 返回唯一元素的个数，即 i + 1return i + 1;}
}