Wednesday, July 9, 2014

Remove Duplicates from Sorted Array

Basic idea of my code: variable len is used as a index representing where to put an unique element; once an unique, or differernt element is found, set A[len] to be this value. Since it is a sorted array, we can solve this problem in this way. Totally, time complexity should be O(n).

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A == null) return 0;
        if (A.length <= 1) return A.length ;
        int crntPre = A[0];
        int len = 1;
        for(int i = 1; i < A.length; i ++){
            if(crntPre != A[i]){
                // set element at swapTo to be A[i]
                A[len] = A[i];
                len ++;
                crntPre = A[i];
            }
        }
        return len;
    }
}

No comments:

Post a Comment