[Leetcode] 52. Remove Duplicates

题目

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.

解题之法

class Solution {
public:
    int removeDuplicates(vector<int>& A) {
        int n = A.size();
        if (n <= 2) return n;
        int pre = 0, cur = 1, count = 1;
        while (cur < n) {
            if (A[pre] == A[cur] && count == 0) ++cur;
            else {
                if (A[pre] == A[cur]) --count;
                else count = 1;
                A[++pre] = A[cur++];
            }
        }
        return pre + 1;
    }
};

分析

这道题是之前那道 Remove Duplicates from Sorted Array 有序数组中去除重复项 的延续，这里允许最多重复的次数是两次，那么我们就需要用一个变量count来记录还允许有几次重复，count初始化为1，如果出现过一次重复，则count递减1，那么下次再出现重复，快指针直接前进一步，如果这时候不是重复的，则count恢复1，由于整个数组是有序的，所以一旦出现不重复的数，则一定比这个数大，此数之后不会再有重复项。