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

【LeetCode_26】删除有序数组中的重复项

ai 2025/9/3 10:27:12

刷爆LeetCode系列

LeetCode26题：
github地址
前言
题目描述
题目与思路分析
代码实现
算法代码优化

LeetCode26题：

github地址

有梦想的电信狗

前言

本文介绍用C++实现leetCode第26题
题目链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

题目描述

在这里插入图片描述

题目与思路分析

目标分析：

将数组中重复的元素移除，仅保留一份
原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1)
返回nums中与唯一元素的个数

思路：双指针

src：指向待扫描元素，从第二个元素开始扫描
- 因为第一个元素一定不是重复的，因此初始下标为1
dst：dst下标及其之前，都是不重复的元素
- dst指向不重复元素中的最后一个，初始下标为0
count：记录赋值的次数，赋值的次数即为除去第一个元素后，其余元素中的元素的种类，初始值为1

操作：

给定的数组是有序的，保证了我们不会遇到先前处理过的元素
nums[src] != nums[dst] 时，说明：src位置的数第一次出现，将其放在dst的下一个位置。
- dst先++，指向下一个不重复元素的位置
- nums[dst] = nums[src]：向nums[dst]赋值放入元素，之后src++
- 计数器count++
nums[src] == nums[dst] 时，说明src位置的数之前出现过了，为重复元素，src++略过该元素。

在这里插入图片描述

代码实现

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;int count = 1;while(src < nums.size()){if(nums[src] == nums[dst]){++src;}else{++dst;nums[dst] = nums[src];++src;++count;}}return count;}
};

算法代码优化

时间复杂度：O(n)
空间复杂度：O(1)

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;int count = 1;while(src < nums.size()){if(nums[src] == nums[dst]){++src;}else{++dst;nums[dst] = nums[src];++src;++count;}}return count;}
};

通过观察我们发现：

循环内dst和count自增的次数一样，且初值分别为0和1，因此count == dst + 1
- dst指向的是数组中不重复的最后一个元素，dst + 1即为不重复的元素的个数
且while循环内，if和else逻辑中，都执行了src++，因此if和else中的src++可以省略，直接将src在循环中++

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;while(src < nums.size()){if(nums[src] != nums[dst]){++dst;nums[dst] = nums[src];}++src;}return dst + 1;}
};

利用前置和后置++的特性最终优化，虽然代码更加简洁了，但不推荐这么写，因为算法的可读性下降了

class Solution {
public:int removeDuplicates(vector<int>& nums) {int src = 1, dst = 0;while(src < nums.size()){if(nums[src] != nums[dst]){nums[++dst] = nums[src];}++src;}return dst + 1;}
};