Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?
What if duplicates are allowed at most twice?
For example,
Given sorted array A =
Given sorted array A =
[1,1,1,2,2,3],
Your function should return length =
The same idea with the former one, also use two pointer, and sweep all duplicate elements, use a count to check if we have duplicate, if we have, then just make a copy of that duplicate.
5, and A is now [1,1,2,2,3]. public int removeDuplicates(int[] A) {
int n = A.length;
if(n < 3)
return n;
int p1 = 0, p2 = 1;
while(p2 < n) {
int cnt = 1;
while(p2 < n && A[p2] == A[p1]) {
p2++; cnt++;
}
if(cnt >= 2) {
p1++;
A[p1] = A[p1-1];
}
if(p2 == n) break;
p1++;
A[p1] = A[p2];
p2++;
}
return p1+1;
}
没有评论:
发表评论