80. 删除有序数组中的重复项 II Python_图解80. 删除有序数组中的重复项 ii

一、题目描述

给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使得出现次数超过两次的元素只出现两次 ，返回删除后数组的新长度。

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

示例 1

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

提示：
1 <= nums.length <= 3 * 10^4
-10^4 <= nums[i] <= 10^4
nums 已按升序排列

二、代码

代码如下：

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        count = 0
        max_num = 10001
        flag = nums[0]
        path = 1
        for i in range(len(nums)-1):
            if nums[i] == max_num:
                path = 1
                continue
            else:
                if nums[i] == nums[i+1]:
                    path = path + 1
                else:
                    flag = nums[i+1]
                    path = 1
                if path == 3:
                    for j in range(len(nums[i+1:])):
                        if nums[i+1+j] == flag:
                            nums[i+1+j] = max_num
                            count = count + 1
                        else:
                            flag = nums[i+1+j]
                            print(flag)
                            break
                    path = 1
        nums.sort()
        if count != 0:
            for i in range(count):
                nums.pop()
        return len(nums)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

三、解题思路

本题难点在于使用原地算法修改数组，解题的大思路为：首先找出并“标记”数组中所有超出2个重复元素的元素，然后将这些已标记的元素全部删除。
本题解采用for循环遍历数组，如果遇到了重复元素超出2个的元素，就将其替换为一个特殊的数（例如本题解将其替换为数字范围10⁴以外的数10001），顺便记录一下替换的次数count，最后将数组重新排序（使得这些被替换的数都处在数组末尾），然后使用pop函数重复count次将其全部删除。
流程以nums=[0,0,1,1,1,1,2,3,3]为例：
①[0, 0, 1, 1, 1, 1, 2, 3, 3] 原始nums数组
②[0, 0, 1, 1, 10001, 10001, 2, 3, 3] 替换所有重复数字超过2个的元素
③[0, 0, 1, 1, 2, 3, 3, 10001, 10001] 重新排序
④[0, 0, 1, 1, 2, 3, 3] 删除末尾的特殊数字
需要注意的是，本题重新排序数组时采用的函数为sort()函数，属于原地排序，满足题意。