80. Remove Duplicates from Sorted Array II

Q:
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].


A:
-----------------------------------------3 rd Pass ----------------------
错误：   没有注意到， 如果直接覆盖的话，会有重复的---------------------------------

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if(nums.size()<2)
            return nums.size();
        int pre = 1;
        for(int i =2;i<nums.size();i++)
            if(nums[i] != nums[pre]  || nums[i] != nums[pre-1])
                nums[++pre] = nums[i];
        
        return pre+1;
    }
};

-----------------------2 rd pass ----------------------

public class Solution {
    public int removeDuplicates(int[] A) {
        if (A.length <= 1)
            return A.length;
        int i = -1, j = 0;
        while (j < A.length) {
            if (j + 1 < A.length && A[ j] == A[j + 1]) {
                A[++i] = A[j++];
            }
            // move to the last appearance of A[j]
            while (j + 1 < A.length && A[ j ] == A[j + 1]) {
                j++;
            }
            i++;
            A[i] = A[j];
            j++;
        }
        return i + 1;
    }
}

-----------------------------------------1 rd Pass ----------------------
多加了个flag, 来标记，是否刚刚找到个重复的。

 如果是，则跳两位， 否则跳一位。

public class Solution {
    
    public int removeDuplicates(int[] A) {
        if(A.length <= 2){
            return A.length;
        }
        //A at least has three elements
        int pointer=0 , runner=1;
        while(runner<A.length){
            boolean findRepeats = false;
            while(runner<A.length && A[runner] == A[pointer]){
                findRepeats = true;
                runner++;
            }
            if(runner >= A.length){
                //if already found the duplicates
                if(findRepeats){
                    pointer++;
                    A[pointer] = A[runner-1];
                }
                break;
            }
            //now pointer value and runner value are not equal
            if( !findRepeats ){
                pointer++;
                A[pointer] = A[runner];
            }else{ // findRepeats, and we will allow 2 spaces            
                A[pointer+1] = A[pointer];// coz there are repeats
                A[pointer+2] = A[runner];
                pointer = pointer+2;
            }
            runner++;
        }
        return pointer+1;
        }
}