题目链接：Remove Duplicates from Sorted Array II

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].

这道题的要求是删除有序数组中的重复元素，使其重复元素最多出现2次，返回删除后数组长度。

这道题是Remove Duplicates from Sorted Array的第二版，区别就是这题要求重复元素最多出现2次。当然，也可以扩展到重复元素最多出现k次。这里就按k次说明思路。

添加计数器变量cnt，用于统计重复元素出现的次数。如果当前元素和前面元素不同，则说明该元素尚未重复，cnt置1；如果当前元素和前面元素相同，则说明该元素是重复的，此时如果cnt小于k，则加1，否则不保留该元素。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution
{
public:
    int removeDuplicates(int A[], int n)
    {
        return removeDuplicates(A, n, 2);
    }
private:
    int removeDuplicates(int A[], int n, int k)
    {
        if(n <= k)
            return n;
        
        int i = 1;
        for(int j = 1, cnt = 1; j < n; ++ j)
            if(A[j] != A[j - 1] || cnt < k)
            {
                cnt = A[j] != A[j - 1] ? 1 : cnt + 1;
                A[i ++] = A[j];
            }
        return i;
    }
};