LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

题目描述

80 Remove Duplicates from Sorted Array II
https://leetcode-cn.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.

---

解题过程

相似题目
LeetCode.283.Move Zeroes 将数组中的零移到末尾
LeetCode.027.Remove Element 从数组中移除指定元素
LeetCode.026.Remove Duplicates from Sorted Array 删除有序数组中的重复项
LeetCode.080.Remove Duplicates from Sorted Array II 删除有序数组中的重复项2

快慢双指针，左指针left左边是数组中要保留的，右指针right指向当前遍历的元素。
计数器count维护right的重复次数。
当right和前一个数相同且count<=2时，right覆盖left；当count>2时，right右移，left不动，跳过重复超过2次的数。
当right和前一个数不同时，righ覆盖left，count清零重新计数。

时间复杂度 O(n)，空间复杂度 O(1)

private static class SolutionV2020 {
    public int removeDuplicates(int[] nums) {
        if (null == nums) {
            return 0;
        }
        if (nums.length < 3) {
            return nums.length;
        }
        int left = 0, count = 0;
        for (int right = 1; right < nums.length;) {
            if (nums[right] == nums[right - 1]) {
                // 和前一个数相同
                if (count == 0) {
                    // 第二个重复的，不算重复
                    nums[++left] = nums[right++];
                    count++;
                } else {
                    count++;
                    right++;
                }
            } else {
                // 和前一个数不同，count清零
                count = 0;
                nums[++left] = nums[right++];
            }
        }
        return left + 1;
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_080_RemoveDuplicatesFromSortedArray2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_080_RemoveDuplicatesFromSortedArray2.java

---