Wednesday, April 9, 2014

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].
Solution: 
 Same as Problem I,  only need one flag to remember how many times one number happens. 
Code:
    int removeDuplicates(int A[], int n) {
            int cval;  // current compare value
    int cnt;
    int flag;

    if (n==0 || n==1) return n;

    cval = A[0];
    cnt=1;
    flag=0;  // happen once
    for(int i=1; i
    {
        if(A[i]!=cval)
        {
            A[cnt]=A[i];
            cnt++;
            cval=A[i];
            flag=0;
        }
        else
        {
            if(flag==0)
            {
                A[cnt]=A[i];
                cnt++;
                flag++;
            }
        }
    }
    return cnt;

No comments:

Post a Comment