[LeetCode] 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].

 

问题描述：跟前面的Remove Duplicates类似，需要删除已经排序的数组中的重复元素，不过这里有另外一个条件：每个元素最多可以允许有两次，如上面的例子。

 

其实方法跟前面的一样，用一个变量遍历数组，用另一个变量指向已经经过处理满足条件的数组，这里需要引入另外一个保存计数的变量。

 

 

class Solution {  
public:  
    int removeDuplicates(int A[], int n) {  
        // IMPORTANT: Please reset any member data you declared, as  
        // the same Solution instance will be reused for each test case.  
        int i = 0, j = 0, cnt = 0;  
          
        if(n == 0 || n == 1)  
            return n;  
          
        for(i = 0; i < n-1; ++i) {  
            if(A[i] == A[i+1] && cnt < 2) {  
                A[j++] = A[i];  
                cnt++;  
            }  
            else if(A[i] == A[i+1] && cnt >= 2) {  
                cnt++;  
            }  
            else if(A[i] != A[i+1] && cnt < 2) {  
                A[j++] = A[i];  
                cnt = 0;  
            }  
            else if(A[i] != A[i+1] && cnt >= 2) {  
                cnt = 0;  
            }  
        }  
          
        if(A[n-1] != A[n-2] || A[n-1] == A[n-2] && cnt < 2)  
            A[j++] = A[n-1];  
          
        return j;  
    }  
};  

 

 

上面对四种情况进行分类讨论，当前元素与下一个元素相等且计数小于2时，将当前元素加入数组中，并将计数值加1；当前元素与下一个元素相等且计数大于或等于2时，不将当前元素加入到数组中，但将计数值加1，其实这里也可以什么也不做；当前元素与下一个元素不等且计数小于2时，将当前元素加入到数组中，并将计数值清0；当前元素与下一个元素不登且计数大于2时，将计数值清0。

这里要考虑边界情况：最后一个元素没有下一个元素，因此，最后一个元素要单独拿出来，在讨论最后一个元素时用到了A[n-2]，因此，这里又要将n==0和1两种情况也拿出来。

 

补充：软件开发 , Java ,