Search This Blog

Monday, December 10, 2012

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

public class Solution {
    public int removeDuplicates(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A.length<=2) return A.length;
        int i=2, j=1;
        int[] buf = new int[2];
        buf[0] = A[0];
        buf[1] = A[1];
        
        while(i<A.length){
            if(A[i]>buf[1] || (A[i]==buf[1] && A[i]>buf[0])){
                if(A[i]==buf[1]) buf[0]=A[i];
                buf[1]=A[i];
                i++;
                j=Math.max(1,j-1);
            }else if(i+j<A.length){
                    int temp=A[i+j];
                    A[i+j]=A[i];
                    A[i]=temp;
                    j++;
            }else break;
        }
        return i;
    }
}

No comments: