[Leetcode]80. 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.

例子

例子 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.

例子 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.

解题思路

这道题的要求和前一道题比较类似，区别是对每个数可以最多保持两位。通过前一道题的思路，同样可以采用快慢指针的思路，只需要额外增加一个变量用来保存出现过次数即可，代码如下：

int removeDuplicates(vector<int>& nums) {
    if (nums.empty()) {
        return 0;
    }

    int slow = 0, count = 1;
    for (int fast = 1; fast < nums.size(); fast++) {
        if (nums[fast] != nums[slow]) {
            nums[++slow] = nums[fast];
            count = 1;
        }
        else if (count < 2) {
            nums[++slow] = nums[fast];
            count++;
        }
    }

    return slow + 1;
}

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