80. Remove Duplicates from Sorted Array II

全栈程序员-站长 • 2022年4月2日下午12:00 • 未分类 • 阅读 49

大家好，又见面了，我是你们的朋友全栈君。

80. Remove Duplicates from Sorted Array II

题目

 Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

解析

参考ref nowcoder

方法一：很灵活的方法，扩展性较强，如果将occur<2 改为   occur<3  ，就变成了允许重复最多三次
    
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=2) return n;
        int index=2;//允许重复两次，可以修改为三次
        for(int i=2;i<n;i++)
        {
            if(A[i]!=A[index-2])//允许重复两次，可以修改为三次
                A[index++]=A[i];
        }
         
        return index;
    }
};

方法二：简洁版本

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        int index=0;
        for(int i=0;i<n;i++){
            if(i>0&&i<n-1&&A[i]==A[i-1]&&A[i]==A[i+1])
                continue;
             
            A[index++]=A[i];
        }
         
        return index;
    }
};

// 80. Remove Duplicates from Sorted Array II
class Solution_80 {
public:
    int removeDuplicates_(vector<int>& nums) {

        if (nums.size()<=1)
        {
            return nums.size();
        }

        int len = 0;
        int start = 0, end = 0;

        for (int i = 1; i < nums.size();i++)
        {
            if (nums[i]==nums[i-1])
            {
                end++;
            }
            else
            {
                start = i;
                end = i;
            }
            if (end-start+1<=2)
            {
                nums[++len] = nums[i];
            }
        }
        
        return len+1;
    }

    int removeDuplicates(int A[], int n) {
        
        vector<int> vec(A, A + n); //vec传值不能达到A；
        return removeDuplicates_(vec);
    }

    int removeDuplicates_1(int A[], int n) {
        int *nums = A;
        if (n <= 1)
        {
            return n;
        }

        int len = 0;
        int start = 0, end = 0;

        for (int i = 1; i < n; i++)
        {
            if (nums[i] == nums[i - 1])
            {
                end++;
            }
            else
            {
                start = i;
                end = i;
            }
            if (end - start + 1 <= 2)
            {
                nums[++len] = nums[i];
            }
        }

        return len + 1;
    }


};