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