删除重复项

Leetcode算法练习第二十六题：删除重复项

问题描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。

解法

使用双指针pre 和p分别指向第一个不重复的元素和当前循环元素，则在循环指针移动的时候判断值是否相同，若相同，移动交换pre和p 指针所指向的内容，然后后移pre和p，否则，只后移p指针。重复以上过程直至p到达数组末尾。返回pre+1即为新数组大小

复杂度

首先至少要遍历一遍数组，故时间复杂度为O(n)，而空间上只需要原地交换元素即可，复杂度O(1)。

C++

static const auto io_sync_off=[](){
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(size(nums)<=1)return size(nums);
        
        int p=1,pre=0,len=size(nums);
        while(p<len){
            if(nums[pre]==nums[p])
                p++;
            else{
                nums[pre+1]=nums[p];
                p++;
                pre++;
            }
        }
        return pre+1;        
    }
};

Python

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if nums is None:
            return
        if len(nums)<=1:
            return len(nums)
        pre=p=0
        LEN=len(nums)
        while p<LEN:
            if p==pre:
                p+=1
                continue
            if nums[p]==nums[pre]:
                p+=1
            else:
                nums[pre+1]=nums[p]
                p+=1
                pre+=1
        return pre+1