Sunday, September 15, 2013

Remove Duplicates from Sorted Array

Q: 
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2].




 A: 

public class Solution {
    public int removeDuplicates(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if(A==null)return 0;
        if(A.length <= 1){
            return A.length;
        }
        //A at least has two elements
        int pointer=0 , runner=1;
        while(runner<A.length){
            while(runner<A.length && A[runner] == A[pointer]){
                runner++;
            }
            if(runner >= A.length){
                break;
            }
            //now pointer value and runner value are not equal
            A[pointer+1] = A[runner];
            runner++;
            pointer++;
        }
        
        return pointer+1;
        
        
    }
}




Mistakes: 
 1:判断了A。length ==1 和A ==null的情况,确忘了判断A。length ==0,哎


---------------- 第二遍----------------

public class Solution {
    public int removeDuplicates(int[] A) {
        int i= -1, j = 0;// i is the just valid position, j is the to be searched position
        while(j<A.length){
            // find the last j of the same value
            while(j+1<A.length && A[j+1]==A[j]){
                j++;
            }
            // now A[j] is valid, and could be copied to A[i]
            i++;
            A[i]=A[j];
            j++;
        }
        return i+1;
    }
}

-------------------------3 rd pass

public class Solution {
    public int removeDuplicates(int[] A) {
        if(A.length<1)
            return A.length;
        int i = 0; // index that is just set unique
        for(int j =1;j<A.length;j++){
            if(A[j] != A[i]){
                i++;
                A[i]=A[j];
            }
        }
        return i+1;
    }
}



No comments:

Post a Comment