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