### leetcode Question 78: Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II

What if duplicates are allowed at most twice?
For example,
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;
}
};

1. int removeDuplicates(int A[], int n)
{
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;
}

2. This comment has been removed by the author.

3. Hi, I have read your blog for a long time and got really good hints! For this problem, I think we may use less variables : )
int 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;
}

1. copied from another blog..:)

4. This comment has been removed by the author.

int 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;

}