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 =
5
, and A is now [1,1,2,2,3]
.
Algorithm.
This is the same as the previous removeDup one. The difference is that, we need to make
A[cur] = A[cur] - A[cur - 2].
For the next scan, when meet A[j] != 0, means now A[i] = A[i-2] + A[j] and ++i;
My Code:
int removeDuplicates(int A[], int n) {
if(n < 3) return n;
for(int cur = n-1; cur > 1; --cur)
A[cur] = A[cur] - A[cur - 2];
int i = 2;
for(int j = 2; j < n; ++j){
if(A[j]){
A[i] = A[i-2] + A[j];
++i;
}
}
return i;
}
No comments:
Post a Comment