[LeetCode 80] Remove duplicates

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.

Solution

1. 用一个pointer指向需要被替换的位置，另一个pointer指向当前位置。start index == 2.
   比如1，1，1，2，2，2，3
   起始replaceIndex == 2, currentIndex == 2, 每次移动时，当前位置的数与replaceIndex - 2的数比较是否重复，如果不重复，则

nums[replaceIndex] = nums[i];
replaceIndex ++;

如果重复

if (nums[replaceIndex - 2] == nums[i]) {
  // do nothing, don't move replaceIndex
  len --;
  continue;
}

Code

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0 || nums.length < 2) {
            return nums.length;
        }
        
        int replaceIndex = 2;
        int len = nums.length;
        
        for (int i = 2; i < nums.length; i++) {
            // found duplicates
            if (nums[replaceIndex - 2] == nums[i]) {
                // do nothing, don't move replaceIndex
                len --;
                continue;
            } else {
                nums[replaceIndex] = nums[i];
                replaceIndex ++;
            }
        }
        
        return len;
    }
}