Follow up for "Remove Duplicates":

What if duplicates are allowed at most

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;

}