题目描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

样例

示例 1:
给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。

示例 2:
给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。

算法1

(线性扫描) $O(n)$

因为是排好序的，使用快指针从前往后扫描，并记录当前是第几个重复的数，不大于2的，我们都写到慢指针的位置；
最后，慢指针所在位置即为答案。

时间复杂度

线性扫描一遍数组，时间复杂度为$O(n)$

参考文献

C++ 代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size(), l = 0, r = 0, cnt = 1;
        while(r < n){
            // 确认当前是重复元素中的第几个
            if (r > 0 && nums[r] == nums[r - 1]) ++cnt; 
            else cnt = 1;
            // 小于2，就写到慢指针的位置，否则，快指针往后找到下一个不重复的位置
            if (cnt <= 2) nums[l++] = nums[r++];
            else while (r < n && nums[r - 1] == nums[r]) ++r;
        }
        return l;
    }
};

更简洁的实现

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int l = 0;
        for (int num: nums)
            if (l < 2 || num > nums[l - 2])
                nums[l++] = num;

        return l;
    }
};