再看leetcode26--Remove Duplicates from Sorted Array

再看leetcode26--Remove Duplicates from Sorted Array

题目

这个题目之前做过一次,再补充一些东西,后来走在路上又想了想这个问题,其实这个题的困难可能在于边删除的时候数组的长度在变化,而这对于后面的index就会有影响,比如它本来在第10个位置上的,但是前面的有删除的了,所以现在的第10个也变化了,后来我想,如果从后面开始处理的话就不会出现这种情况。

代码如下

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        for(int j=nums.size()-1;j>0;j--){
            
            if(nums[j]==nums[j-1]){
                nums.erase(nums.begin()+j);
            }
        }
        return nums.size();
    }
};

也可以用unique函数

这里如果只是返回最后得到的长度的话,用python里面的return len(set(nums))就搞定了,不过这里要求的是操作的同时,最后的nums必须就是最后的结果,虽然没有要求返回。


class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        auto p = unique(nums.begin(), nums.end());
        nums.erase(p, nums.end());
        return nums.size();
    }
};

用python的话是

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return 1
        for i in range(len(nums)-1, 0, -1):
            if nums[i] == nums[i-1]:
                del(nums[i])
            
        return len(nums)

这个题也可以用双指针的办法

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 这个题不一定非得一定要得到最后的list之后才能知道最后有多少个不同的数
        # 其实只要返回有几个不同的数字就可以了
        # 采用双指针法,都初始化为0,
        if len(nums)==0:
            return 0
        
        slow, fast = 0, 0
        n = len(nums)
        
        while fast<n:
            if nums[slow] == nums[fast]:
                # 些时快指针往前走
                fast += 1
            else:
                slow += 1  # 些时慢的向前走一步,并把fast处的值挪过来
               
                nums[slow] = nums[fast]
                
                # 然后fast也要往前走一步,
                fast += 1
                
        # 最终fast走到底的时候,slow+1就是不同的元素的个数,因为slow指的是index,加1才是对的
        return slow +1

上面的可以改一下成为下面的这种样式

class Solution:
    def removeDuplicates(self, nums:List[int]) -> int:
        if len(nums) == 0:
            return 0
        slow, fast = 0, 0
        n = len(nums)

        while fast < n:
            if nums[slow] != nums[fast]:
                slow += 1
                nums[slow] = nums[fast]

            fast += 1

        return slow+1   # 因为slow与fast都是index, 而最终要返回的index.

打赏,谢谢~~

取消

感谢您的支持,我会继续努力的!

扫码支持
扫码打赏,多谢支持~

打开微信扫一扫,即可进行扫码打赏哦