题目: 删除有序数组中的重复项 II

分析

方法一：双指针

我们可以使用两个指针 i 和 j。其中 i 是慢指针，而 j 是快指针。只要 nums[i] == nums[j] 且重复数量不超过 2，我们就可以让 j 自增并保持 i 不变。否则，我们需要递增 i，将 nums[j] 的值复制到 nums[i]，然后递增 j。

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

Python 代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        i, j, count = 0, 1, 1
        while j < len(nums):
            if nums[j] == nums[j - 1]:
                count += 1
            else:
                count = 1
            if count <= 2:
                i += 1
                nums[i] = nums[j]
            j += 1
        return i + 1

方法二：计数法

由于数组中的元素已经按升序排列，所以可以统计每个元素的出现次数。对于每个元素，如果出现次数大于 2，就把多余的元素删除。最后返回数组的长度即可。

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

Python 代码：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        if not nums:
            return 0
        i = 1
        count = 1
        for j in range(1, len(nums)):
            if nums[j] == nums[j - 1]:
                count += 1
            else:
                count = 1
            if count <= 2:
                nums[i] = nums[j]
                i += 1
        return i

方法三：Python内置函数

Python 内置的 Counter 类可以很方便地统计每个元素的出现次数。我们可以使用 Counter 统计每个元素出现的次数，然后遍历数组，将出现次数不超过 2 的元素添加到新的列表中，最后将新的列表复制回原数组。

时间复杂度为 O(n)，空间复杂度为 O(n)。

Python 代码：

from collections import Counter

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        counter = Counter(nums)
        res = []
        for num in nums:
            if counter[num] <= 2:
                res.append(num)
        nums[:len(res)] = res
        return len(res)

以上是三种解决方法，其中方法一和方法二时间复杂度和空间复杂度都是 O(n)，方法三的时间复杂度和空间复杂度都是 O(n)。