Problem

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.

Analysis

At first I was thinking about using unordered_map template in STL. Unordered_map allows us to access the elements using only O(1) time. However, when I almost finished my unordered_map version of this solution, I find out that the same thing can be done by simply sort the array. What's more, when I read the problem again, I finally noticed the array is already sorted, which makes this problem much easier. What I need to do is scan the array and record the numbers of every elements' appearance. If the number is less or equal than 2, I'll simply add it to the final result, if not, just add 2.

As a matter of fact, when I almost finished my second edition, I find out that I'm also required to produce the array, not just output the length of the array. Simply delete it from vector will cost O(n^2) time, which is apparently not good enough. Producing it in a new vector and than copy it back will probably be a good choice with O(n) time consuming. However, is there an O(n) method with only O(1) required space?

The solution is provide two pointers. One is pointed to the end of the valid part of the array, the other is pointed to the end of the scanned part of the array. Thus, we can do the scanning and copying simultaneously at the same memory space.

Implementation

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.empty()) return 0;
        int p=1, num=nums[0], times=1;
        for(int i=1; i<nums.size(); i++){
            if(nums[i]==num){
                if(++times<=2)
                    nums[p++] = num;
            }
            else{
                num = nums[i];
                times = 1;
                nums[p++] = num;
            }
        }
        return p;
    }
};

Read the problem carefully!