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

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

article 2024/12/4 16:02:31

题目链接：

https://leetcode.cn/problems/remove-duplicates-from-sorted-array/description/?envType=study-plan-v2&envId=top-interview-150

题目描述：

在这里插入图片描述
解题思路：

使用双指针算法（快慢指针），p1与p2分别指向第一个和第二个元素，p2为快指针，p1为慢指针。

当nums.size() == 0时，直接return 0; 即可
当nums.size() !=0时，p1作为慢指针指向第一个元素，p2作为快指针指向第二个元素,res 初始化为1
当nums[p1] == nums[p2] 时，只需要将p2++即可
当nums[p1] != nums[p2]时，只需要将p+1位置的元素与p2交换，同时指针p1和p2都移向下一个元素，由于此时优找到了一个新元素，因此res也要加1
当p2指针超过nums.size()，说明数组遍历完成，结束循环

代码实现：

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

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();

        if (n==0){
            return 0;
        }

        int p1 = 0;
        int p2 = 1;
        int res = 1;

        while(p2<n){
            if(nums[p1] == nums[p2]){
                p2++;
            }
            else{
                p1++;
                nums[p1] = nums[p2];
                p2++;
                res++;
            }
        }

        return res;
    }
};