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].
Idea: Use two pointers i, j. i points to the index of last valid number. Use j to scan the array from left to right. If num[i]==num[i-1]==num[j], "continue"; otherwise copy num[j] to num[++i].
Time: O(n) Space: O(1)
Code:
public class Solution {
public int removeDuplicates(int[] A) {
if(A==null)
return 0;
if(A.length<=2)
return A.length;
int i=1;
for(int j=i+1;j<A.length;j++)
{
if(A[i]==A[i-1]&&A[i]==A[j])
continue;
else
A[++i]=A[j];
}
return i+1;
}
}
No comments:
Post a Comment