80. Remove Duplicates from Sorted Array II Leetcode
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].
Solution:
Follow up for
26. Remove Duplicates from Sorted Array Leetcode
An additional counter is needed to track the numbers of duplicates, once the counter is greater than 2, do not increment the index until a new value occur.
Time complexity: O(n)
public int removeDuplicates(int[] A) {
if(A==null) return 0;
if(A.length<=2) return A.length;
int count=1;
int ind=1;
for(int i=1;i<A.length;i++){
if(A[i]==A[i-1]) {
count++;
if(count<3) A[ind++]=A[i];
}
else {
A[ind++]=A[i];
count=1;
}
}
return ind;
}
No comments:
Post a Comment