Wednesday, January 29, 2014

[leetcode] 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].
Algorithm.
This is the same as the previous removeDup one. The difference is that, we need to make 
A[cur] = A[cur] - A[cur - 2].
For the next scan, when meet A[j] != 0, means now A[i] = A[i-2] + A[j] and ++i;
My Code:
int removeDuplicates(int A[], int n) {
        if(n < 3) return n;
        for(int cur = n-1; cur > 1; --cur)
            A[cur] = A[cur] - A[cur - 2];
        int i = 2;
        for(int j = 2; j < n; ++j){
            if(A[j]){
                A[i] = A[i-2] + A[j];
                ++i;
            }
        }
        return i;
    }

No comments:

Post a Comment