• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

80. Remove Duplicates from Sorted Array II

开发技术 开发技术 2周前 (04-06) 8次浏览

仅供自己学习

思路:
题目要求原地算法,在考虑因为最大有两个重复元素。那么我们运用双指针,一个用来记录遍历过且修改为不重复的数组长度slow,一个用来记录当前位置的fast指针。这个问题容易找到超过两个元素的重复元素,但是如何去掉是个问题。
因为我们允许重复两个,那么我们每次判断都是slow-2的元素和fast判断, 如果fast和slow-2的元素相等,那么slow不变,直到fast找到不等的,然后slow的位置就被fast位置的元素代替,那么连续的元素就会被中断只有两个元素,又因为是有序的,后面的元素肯定和重复的不同,所以会一直将重复的覆盖掉,然后slow加一。fast不管slow-2如何都会加一,因为是要一直遍历的。
最后 nums[0]~nums[slow]的元素都是删重复元素后得到的,slow也是长度。

代码:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int slow=2,fast=2;
        int n=nums.size();
        if(n<2) return n;
        while(fast<n){
            if(nums[slow-2]!=nums[fast]){
                nums[slow]=nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};

上述可优化

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int i=0;
        if(nums.size()<2) return nums.size();
        for(auto& num:nums){  //因为从头开始遍历,所以i也需要等于0
            if(i<2||nums[i-2]<num){  //这里i<2的条件是为了解决numS[i-2],i-2小于0的问题,比较用小于是因为是升序,只要小于肯定不相等
                nums[i++]=num;
            }
        }
        return i;
    }
};

程序员灯塔
转载请注明原文链接:80. Remove Duplicates from Sorted Array II
喜欢 (0)