Leetcode - 80. 删除有序数组中的重复项 II

给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1)额外空间的条件下完成。

说明：
为什么返回数值是整数，但输出的答案是数组呢？
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。
你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中 该长度范围内 的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

示例 1：

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]
解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]
解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。

提示：

• 1 <= nums.length <= 3 * 10⁴
• -10⁴ <= nums[i] <= 10⁴
• nums 已按升序排列

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解1 2021/9/11 O(n)

from collections import defaultdict

def removeDuplicates(nums: list) -> int:
    len=nums.__len__()
    if len<=2: return len
    # 题目说了不能用额外空间，l,r移动覆盖着正常解就行了
    # 懒得写了，用dict简单点
    # nums本身就是升序的
    d=defaultdict(int)
    for x in nums:
        d[x]+=1
    i=0
    for x in d.keys():
        nr=d[x] if d[x]<=2 else 2
        while nr:
            nums[i]=x
            i+=1
            nr-=1
    return i

if __name__ == ‘__main__‘:
    # 5, nums = [1,1,2,2,3]
    nums = [1, 1, 1, 2, 2, 3]
    print(removeDuplicates(nums),nums)
    # 7, nums = [0,0,1,1,2,3,3]
    nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
    print(removeDuplicates(nums),nums)
    nums = [0]
    print(removeDuplicates(nums),nums)

Leetcode - 80. 删除有序数组中的重复项 II

原文：https://www.cnblogs.com/Code2235/p/15253739.html