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]
.Analysis:
Just like the idea of previous problem (see Remove Duplicates from Sorted Array)
But add another flag store the number of duplicated elements.
Details can be seen in code.
Code:
class Solution { public: int removeDuplicates(int A[], int n) { // Start typing your C/C++ solution below // DO NOT write int main() function if (n==0){return 0;} if (n==1){return A[0];} int pre=A[0]; int pos = 0; int m=n; int i=1; int count =0; while (i<m){ if (A[i]==pre){ count ++; if (count <2){ i++; }else{ m=m-1; for (int j=pos+1; j<m;j++){ A[j]=A[j+1]; } } }else{ count =0; pre=A[i]; pos=i; i++; } } return m; } };
int removeDuplicates(int A[], int n)
ReplyDelete{
if(n <= 1) return n;
int nidx = 0;
int IsEx = 1;
for(int i = 1; i < n ; i++)
{
if(A[nidx] == A[i] && IsEx < 2)
{
IsEx++;
A[++nidx] = A[i];
}else if(A[nidx] != A[i])
{
IsEx = 1;
A[++nidx] = A[i];
}
}
return nidx + 1;
}
This comment has been removed by the author.
ReplyDeleteHi, I have read your blog for a long time and got really good hints! For this problem, I think we may use less variables : )
ReplyDeleteint removeDuplicates(int A[], int n) {
if(n<3) return n;
int end = 1;
for(int i=2; i < n; i++) {
if(A[i] != A[end-1]){
A[++end] = A[i];
}
}
return end+1;
}
copied from another blog..:)
DeleteThis comment has been removed by the author.
ReplyDeleteHow about this ?
ReplyDeleteint removeDuplicates(vector& nums) {
int n = nums.size();
if(n < 2)
return n;
int count = 0;
for(int i=0; i < n-1; i++){
if(nums[i] == nums[i+1]){
count++;
if(count >= 2){
nums[i] = INT_MAX;
}
}else{
count = 0;
}
}
sort(nums.begin(), nums.end());
count = 0;
for(int i=0;i<n;i++){
if(nums[i]==INT_MAX)
count++;
}
return n-count;
}