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; }
没有评论:
发表评论