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-placewith 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]);
}

Analysis

Remove Duplicates from Sorted Array 的后续，同样是在sorted array中去除重复元素，这里不同在于能够允许k（k=2）个重复。

那么就可以利用一个额外的counter，来计数当前重复元素的次数，达到2以后就跳过store或者swap的过程，直到遇到下一个新的非重复的元素。

其实可以跳出每个pointer移动的细节，如下解法提供了一种另辟蹊径的通用思路 （@StefanPochmann）：

Just go through the numbers and include those in the result that haven't been included twice (or K times) already.

class Solution {

    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }

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

通过以上解法可以发现，其实两个指针的解法，真的很灵活。而且，不一定要同时用while语句，一个指针用for-loop遍历全部，另一个内部循环个根究条件移动也是可行的。

Solution

Two Pointers (6ms, 96.59%)

class Solution {
    public int removeDuplicates(int[] nums) {
        int i = 0;
        int count = 1;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] == nums[i]) {
                if (count < 2) {
                    i++;
                    nums[i] = nums[j];
                    count++;
                } else {
                    continue;
                }
            } else if (nums[j] != nums[i]) {
                i++;
                nums[i] = nums[j];
                count = 1;
            }
        }
        return i + 1;
    }
}

-- for k-allowed k duplication - generic solution

class Solution {
    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }

    public int removeDuplicates(int[] nums, int k) {
        int i = 0;
        int count = 1;
        for (int j = 1; j < nums.length; j++) {
            if (nums[j] == nums[i]) {
                if (count < k) {
                    i++;
                    nums[i] = nums[j];
                    count++;
                } else {
                    continue;
                }
            } else {
                i++;
                nums[i] = nums[j];
                count = 1;
            }
        }
        return i + 1;
    }
}

LeetCode 上的一个对于Remove Duplicates from Sorted Array I，II 通用的答案：（k = 1, or, k = 2）

O(n) time, and O(1) space

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.

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

*Most Simpler Solution (6ms)

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

Could be applied to k - general solution

class Solution {

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

Another implementation:

class Solution {
    public int removeDuplicates(int[] nums) {
        return removeDuplicates(nums, 2);
    }
    private int removeDuplicates(int[] nums,int k) {
        // if array size is less than k then return the same
        if(nums.length < k) {
            return nums.length;
        }
        int i, j;
        // start from index k
        for(i = k, j = k ; j < nums.length; j++) {
            if(nums[i - k] != nums[j]) {
                nums[i++] = nums[j];
            }
        }
        return i;
    }
}

Reference

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/27970/Share-my-O(N)-time-and-O(1)-solution-when-duplicates-are-allowed-at-most-K-times