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].
Idea: Use two pointers i, j. i points to the last unique number, use j to scan the array from left to right. Since this is a sorted array, whenever num[j]!=num[i], it indicates a new unique number. We increase i by 1 and copy num[j] to the new position i pointing at, then continue increasing j. When j finishes scanning all the numbers, return the result.
Time: O(n) Space: O(1)
Code:
public class Solution {
public int removeDuplicates(int[] A) {
if(A==null||A.length==0)
return 0;
int i=0;
for(int j=i+1;j<A.length;j++)
{
if(A[i]!=A[j])
A[++i]=A[j];
}
return i+1;
}
}
No comments:
Post a Comment