首页 > 代码库 > LeetCode: Remove Duplicates from Sorted Array II [080]

LeetCode: Remove Duplicates from Sorted Array II [080]

【题目】



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

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

Your function should return length = 5, and A is now [1,1,2,2,3].



【题意】

给定一个有序数组,给数组去重,和Remove Duplicates from Sorted Array不同
本题允许每个元素最多重复两次,也就是说如果某个元素出现了3次,则我们删除重复的一个,剩下2个元素。


【思路】

维护1个指针p1和一个计数变量counter
p1指向消重后数组尾
counter用于记录当前元素出现的次数


【代码】

class Solution {
public:
    int removeDuplicates(int A[], int n) {
        if(n<=2)return n;
        int p1=1;
        int counter=1;
        
        for(int i=1; i<n; i++){
            if(A[i]==A[i-1]){
                counter++;
                if(counter<=2){A[p1]=A[i]; p1++;}
            }
            else{
                counter=1;
                A[p1]=A[i];
                p1++;
            }
        }
        return p1;
    }
};