11/21/2012

Remove Duplicates from Sorted Array II

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].
class Solution {
public:
    int removeDuplicates(int A[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (A == NULL || n == 0) return 0;
        int i = 1, j = 1, count = 1;
        
        while (j < n) {
            if (A[j] != A[j - 1]) {
                A[i] = A[j];
                ++i;
                count = 1;
            }
            else if (A[j] == A[j - 1] && count < 2) {
                A[i] = A[j];
                ++i;
                ++count;
            }
            else {
                ++count;
            }
            ++j;
        }
        
        return i;
    }
};

No comments:

Post a Comment