80：删除排序数组中的重复项II

问题描述

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素最多出现两次，返回移除后数组的新长度。

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

示例

给定 nums = [1,1,1,2,2,3],

函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。

你不需要考虑数组中超出新长度后面的元素。
1
2
3
4
5

给定 nums = [0,0,1,1,1,1,2,3,3],

函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。

你不需要考虑数组中超出新长度后面的元素。
1
2
3
4
5

思路

这题一开始想的是要从后往前逐渐的覆盖掉。但是这样复杂度太高了。
后来想了个办法，从后往前遍历，这样能少移动点元素。
再后来，想了想这题完全不用移动大量元素。我们只移动该移动的元素即可。怎么做？我们可以设置一个res_length代表结果数组的长度，然后设置计数器i指示当前遍历到了哪个元素。如果这个元素符合我们的移动条件，那么就移动它，否则就跳过它。

AC代码1

class Solution:
    def removeDuplicates(self, nums) -> int:
        length = len(nums)
        i = 0
        while i < length-1:
            cur_data = nums[i]
            j = i+1
            count = 1
            while j < length and nums[j] == cur_data:
                j += 1
                count += 1
            if count > 2:
                i += 2
                i_mirror = i
                for k in range(j,length):
                    nums[i_mirror] = nums[k]
                    i_mirror += 1
                length -= count - 2
            elif count == 2:
                i += 2
            else:
                i += 1
        return length
s = Solution()
nums = [1,2,2,2,3,4,5,5,5,6]
length = s.removeDuplicates(nums)
print(nums[:length])
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

AC代码2

class Solution:
    def removeDuplicates(self, nums) -> int:
        length = len(nums)
        if length <= 2:
            return length
        res_length = 2
        for i in range(2,length):
            if nums[i] == nums[res_length-2]: # 不符合移动条件，跳过
                continue
            else: # 符合移动条件，移动
                nums[res_length] = nums[i]
                res_length += 1
        return res_length
s = Solution()
nums = [1,1,1]
length = s.removeDuplicates(nums)
print(nums[:length])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17