LeetCode 80 - Remove Duplicates from Sorted Array II (Java)

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/

Given a sorted array nums, remove the duplicates in-place such that duplicates appeared at most twice and return the new length.

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

Example 1:

Given nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3 respectively.

It doesn't matter what you leave beyond the returned length.

Example 2:

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

Clarification:

Confused why the returned value is an integer but your answer is an array?

Note that the input array is passed in by reference, which means modification to the input array will be known to the caller as well.

Internally you can think of this:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);

// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

X. https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27970/Share-my-O(N)-time-and-O(1)-solution-when-duplicates-are-allowed-at-most-K-times
Share my O(N) time and O(1) solution when duplicates are allowed at most K times

I think both Remove Duplicates from Sorted Array I and II could be solved in a consistent and more general way by allowing the duplicates to appear k times (k = 1 for problem I and k = 2 for problem II). Here is my way: we need a count variable to keep how many times the duplicated element appears, if we encounter a different element, just set counter to 1, if we encounter a duplicated one, we need to check this count, if it is already k, then we need to skip it, otherwise, we can keep this element. The following is the implementation and can pass both OJ:

int removeDuplicates(int A[], int n, int k) {

            if (n <= k) return n;

            int i = 1, j = 1;
            int cnt = 1;
            while (j < n) {
                if (A[j] != A[j-1]) {
                    cnt = 1;
                    A[i++] = A[j];
                }
                else {
                    if (cnt < k) {
                        A[i++] = A[j];
                        cnt++;
                    }
                }
                ++j;
            }
            return i;
}

https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27976/3-6-easy-lines-C%2B%2B-Java-Python-Ruby
https://leetcode.com/problems/remove-duplicates-from-sorted-array-ii/discuss/27987/Short-and-Simple-Java-solution-(easy-to-understand)

public int removeDuplicates(int[] nums) {
    int i = 0;
    for (int n : nums)
        if (i < 2 || n > nums[i-2])
            nums[i++] = n;
    return i;
}

 public int removeDuplicates(int[] A) {
  if (A.length <= 2)
   return A.length;
 
  int prev = 1; // point to previous
  int curr = 2; // point to current
 
  while (curr < A.length) {
   if (A[curr] == A[prev] && A[curr] == A[prev - 1]) {
    curr++;
   } else {
    prev++;
    A[prev] = A[curr];
    curr++;
   }
  }
 
  return prev + 1;
 }

http://n00tc0d3r.blogspot.com/2013/05/remove-element-from-arraylist.html
So, if you simple change the condition to if (A[i] == A[i-1] && A[i] == A[i-2]), you are trapped!

Why?

In the above problem, we only need to test the one right before the current one which is not possible to have been overwritten. But now, we also need to test the one that is two nodes away which is possible to have been overwritten. That said, we should test the two nodes that are supposed to be ahead of the current node in the new array.

 public int removeDuplicates(int[] A) {  
   int count = 0;  
   for (int i=2; i<A.length; ++i) {  
     if (A[i] == A[i-count-1] && A[i] == A[i-count-2]) { // skip duplicates  
       ++count;  
     } else if (count > 0) { // copy over non-duplicates  
       A[i-count] = A[i];  
     }  
   }  
   return A.length - count;  
 }

http://www.jiuzhang.com/solutions/remove-duplicates-from-sorted-array-ii/

    public int removeDuplicates(int[] nums) {
        // write your code here
        if(nums == null)
            return 0;
        int cur = 0;
        int i ,j;
        for(i = 0; i < nums.length;){
            int now = nums[i];
            for( j = i; j < nums.length; j++){
                if(nums[j] != now)
                    break;
                if(j-i < 2)
                    nums[cur++] = now; 
            }
            i = j;
        }
        return cur;
    }

http://blog.csdn.net/linhuanmars/article/details/24343525
这道题跟Remove Duplicates from Sorted Array比较类似，区别只是这里元素可以重复出现至多两次，而不是一次。其实也比较简单，只需要维护一个counter，当counter是2时，就直接跳过即可，否则说明元素出现次数没有超，继续放入结果数组，若遇到新元素则重置counter。总体算法只需要扫描一次数组，所以时间上是O(n)，空间上只需要维护一个index和counter，所以是O(1)。代码如下： 

public int removeDuplicates(int[] A) {
    if(A==null || A.length==0)
        return 0;
    int idx = 0;
    int count = 0;
    for(int i=0;i<A.length;i++)
    {
        if(i>0 && A[i]==A[i-1])
        {
            count++;
            if(count>=3)
                continue;
        }
        else
        {
            count = 1;
        }
        A[idx++]=A[i];
    }
    return idx;
}

http://simpleandstupid.com/2014/11/06/remove-duplicates-from-sorted-array-ii-leetcode-%E8%A7%A3%E9%A2%98%E7%AC%94%E8%AE%B0/

    public int removeDuplicates(int[] A) {

        int len = A.length;

        if(len <=2 ) return len;

        int index = 2;

        for(int i = index; i < len; i++){

            if(A[i] != A[index-2]){

                A[index] = A[i];

                index++;

            }

        }

        return index;

    }

Read full article from LeetCode – Remove Duplicates from Sorted Array II (Java)