题目链接：80. 删除排序数组中的重复项 II

题解：

与之前一道题几乎类似：LeetCode刷题-26.删除排序数组中的重复项

题目简述：

类似题目是删除排序数组重复项，最多出现一次，这个题是最多出现两次！

要求：使用原地算法，即不开辟额外空间！

题解：

思路：

  • k < 2时，直接存储到原数组
  • k > 2时，判断当前元素和和该元素之前的前两个元素是否相同，若之前已经有两个和当前元素相同，则该元素多余直接跳过，否则累积起来，即nums[k ++ ] = x
  • 最后返回长度k

时间复杂度：O(n)

AC代码：

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 0;
        for(auto& x : nums)
            if(k < 2 || nums[k - 1] != x || nums[k - 2] != x)
                nums[k ++ ] = x;
        return k;
    }
};