题目描述

给定一个有序数组，请删除里面的重复元素，使得每个数最多出现 2次，并返回新数组的长度。
需要使用 原地算法，即最多只能使用额外 $O(1)$ 空间。

样例1

给定数组 = [1,1,1,2,2,3],

你需要返回的长度是5，并且前数组的前5个数是1, 1, 2, 2, 3。

数组中返回长度之后的元素，你可以做任意修改。

样例2

给定数组 = [0,0,1,1,1,1,2,3,3],

你需要返回的长度是7，并且数组的前7个数是0, 0, 1, 1, 2, 3 3。

数组中返回长度之后的元素，你可以做任意修改。

算法

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

由于数组有序，所以相同元素一定是相邻的。
我们定义一个指针 $k$，表示新数组的末尾，然后从前往后扫描原数组，如果当前数不等于 $nums[k]$ 且不等于 $nums[k-1]$，则将当前数插入新数组的末尾。

时间复杂度分析：总共对原数组仅扫描了一遍，所以总时间复杂度是 $O(n)$。

C++ 代码

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.size() < 3) return nums.size();
        int k = 1;
        for (int i = 2; i < nums.size(); i ++ )
            if (nums[i] != nums[k - 1])
                nums[ ++ k] = nums[i];
        k ++ ;
        return k;
    }
};