leetcode Question 78: Remove Duplicates from Sorted Array II

Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
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;
    }
};

6 comments:

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

    ReplyDelete
  2. This comment has been removed by the author.

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

    ReplyDelete
  4. This comment has been removed by the author.

    ReplyDelete
  5. How about this ?

    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;

    }

    ReplyDelete