LeetCode

Remove Duplicates from Sorted Array II

2013.12.26 15:28

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

Solution:

　　We've done the problem "Remove Duplicates from Sorted Array" before, this time the problem allows duplicates for at most twice. My solution is too move the iterator forward by two steps, if the number of consecutive duplicates is no less than 2, thus keeping 2 duplicates in the result array.

　　Time complexity is O(n), space complexity is O(1).

Accepted code:

// 1WA, 1AC
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int i, j, k;

        i = 0;
        k = 0;
        while(i < n){
            j = i + 1;
            while(j < n && A[i] == A[j]){
                ++j;
            }
            // 1WA here, minor change in the if structure will do
            if(j > i + 1){
                // if there're duplicates, allow one more duplicate
                A[k++] = A[i];
                A[k++] = A[i];
            }else{
                A[k++] = A[i];
            }
            i = j;
        }

        return k;
    }
};