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

LeetCode26题：

github地址

有梦想的电信狗

前言

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

题目描述

题目与思路分析

目标分析：

1. 将数组中重复的元素移除，仅保留一份
2. 原地移除，意味着时间复杂度为O(n)，空间复杂度为O(1)
3. 返回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;
    }
};

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！

你的每一次互动，都是对作者最大的鼓励！

---

征程尚未结束，让我们在广阔的世界里继续前行！ 🚀