Thursday, February 20, 2014

Remove Duplicates int Sorted Array (1 & 2)


Remove Duplicates from Sorted Array
For example:
Given input array A = [1,1,2];
Your function should return length = 2, and A is now [1,2].</ br>
Version 1:
public int removeDuplicates(int[] A) {
        if (A.length == 0 || A == null) {
            return 0;
        }
        int size = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != A[size]) {
                size++;
                A[size] = A[i];
            }
        }
        return size + 1;
        
}
Version 2:
public int removeDuplicates(int[] A) {
        if (A == null || A.length == 0) {
            return 0;
        }
        int element = A[0];
        int index = 0;
        for (int i = 0; i < A.length; i++) {
            if (element != A[i]) {
                index++;
                A[index] = A[i];
                element = A[i];
            }
        }
        return index + 1;
        
}
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].
Version 1:
public int removeDuplicates(int[] A) {
        if (A.length <= 2) {
            return A.length;
        }
        int prev = 1;
        int curr = 2;
        while (curr < A.length) {
            if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
                curr++;
            } else {
                prev++;
                A[prev] = A[curr];
                curr++;
            }
        }
        return prev + 1;
        
}
Version 2:
public int removeDuplicates(int[] A) {
       if (A == null || A.length == 0) {
           return 0;
       }

       int size = 0;
       for (int i = 1; i < A.length; i++) {
           if (A[i] == A[size] && size > 0 && A[size - 1] == A[size]) {
               continue;
           }
           A[++size] = A[i];
       }
       return size + 1;
}

No comments:

Post a Comment