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

算法题打卡力扣第26. 删除有序数组中的重复项（easy））

news 2025/8/19 12:05:19

题目描述

在这里插入图片描述

解题思路

想到双指针，使用快慢指针

思路详解：
我们使用两个指针，一个“慢指针” i 和一个“快指针” j。
慢指针 i：它指向新数组（即去重后数组）的末尾。i 左边（包括i）的所有元素都是已经处理好的、不重复的元素。
快指针 j：它负责向前探索，遍历整个原始数组，寻找新的、不重复的元素。

具体步骤：

初始化慢指针 i = 0。快指针 j 从 1 开始遍历数组。
当 j 向前移动时，比较 nums[j] 和 nums[i] 的值。
如果 nums[j] 不等于 nums[i]：
这说明 nums[j] 是一个新的、不重复的元素。
我们首先将慢指针 i 向前移动一位 (i++)。
然后，将 nums[j] 的值赋给 nums[i]，即 nums[i] = nums[j]。这样，新的唯一元素就被添加到了结果数组的末尾。
如果 nums[j] 等于 nums[i]：
这说明遇到了重复元素。
我们什么都不做，只需要让快指针 j 继续向前移动 (j++)，直到找到一个和 nums[i] 不同的元素。
当快指针 j 遍历完整个数组后，i 指向的位置就是最后一个唯一元素的位置。那么，新数组的长度就是 i + 1

代码实现：

int removeDuplicates(int* nums, int numsSize) {int i = 0,j=0;for(int j=0;j<numsSize;j++){if(nums[i]!=nums[j]){i++;nums[i]=nums[j];}}int length = i+1;return length;
}

执行结果
在这里插入图片描述
复杂度分析
时间复杂度：O(n)
空间复杂度：O(1)

为什么这个方法可行？

因为原始数组是有序的。这个前提条件保证了所有重复的元素一定是相邻的。因此，当快指针 j 发现一个与 nums[i] 不同的元素时，这个元素一定是它所在数值区间的第一个，也是唯一一个需要被保留的。
这是一个效率非常高的解法，时间复杂度为 O(n)（因为每个元素最多被访问两次），空间复杂度为 O(1)（因为我们是在原地修改）。
g老师给的更好更标准的答案供大家参考~

int removeDuplicates(int* nums, int numsSize) {// 处理边界情况，如果数组为空，直接返回0if (numsSize == 0) {return 0;}// i 是慢指针，j 是快指针// i 指向新数组的最后一个有效元素的位置int i = 0; // 快指针 j 从第二个元素开始遍历整个数组for (int j = 1; j < numsSize; j++) {// 如果快指针指向的元素与慢指针指向的元素不同if (nums[j] != nums[i]) {// 慢指针向前移动一位i++;// 将新元素的值赋给慢指针的新位置nums[i] = nums[j];}// 如果相同，则快指针 j 继续前进，慢指针 i 保持不动}// 新数组的长度是慢指针的索引值加 1return i + 1;
}