LeetCode 80，不使用外部空间的情况下对有序数组去重

今天是LeetCode专题的第49篇文章，我们一起来看LeetCode的第80题，有序数组去重II(Remove Duplicates from Sorted Array II)。

这题的官方难度是Medium，通过率是43.3%，点赞1104，反对690。这题的通过率有一点点高，然后点赞比也不是很高。说明这题偏容易，并且大家的评价偏低。也的确如此，我个人觉得，大家评价不好的主要原因还是这题偏容易了一些。

题面

其实从题目的标题当中我们已经可以得到很多信息了，实际上也的确如此，这题的题面和标题八九不离十，需要我们对一个有序的数组进行去重。不过去重的条件是最多允许一个元素出现两次，也就是要将多余的元素去掉。并且题目还限制了需要我们在原数组进行操作，对于空间复杂度的要求是O(1)。由于我们去除了元素之后会带来数组长度的变化，所以我们最后需要返回完成之后数组的长度。

这是一种常规的做法，在C++以及一些古老的语言当中数组是不能变更长度的。我们想要在原数组上删除数据，只能将要删除的数据移动到数组末尾，然后返回变更之后的数组长度。这样下游就通过返回的数组长度得知变更之后的数量变化。由于新晋的一些语言，比如Java、Python都支持数组长度变动，所以很少在这些语言的代码当中看到这样的用法了。

样例

Given nums = [0,0,1,1,1,1,2,3,3],

Your function should return length = 7, with the first seven elements of nums being modified to 0, 0, 1, 1, 2, 3 and 3 respectively.

It doesn't matter what values are set beyond the returned length.

在这个样例当中，由于1出现了4次，所以我们需要删除掉2个1，那么删除之后的数组长度也会减少2，所以我们需要返回7，表示删除之后的新的数组的有效长度是7。并且保证原数组当中前5个元素是[0, 0, 1, 1, 2, 3]

题解

删除重复的元素本身并不复杂，唯一麻烦的是我们怎么在不引入额外存储的情况下完成这一点。如果你能抓住数组是有序的这一点，应该很容易想通：既然数组是有序的，那么相同的元素必然排在一起。

既然相同的元素排在一起，那么我们可以利用一个变量存储当前元素出现的次数。如果遇到不同的元素，则将次数置为1。这样我们就可以判断出究竟哪些元素需要删除，哪些元素需要保留了。

但是这就又引入了另外一个问题，我们怎么来删除这些重复的元素呢？因为我们不能引入额外的数组，需要在当前数组上完成。我们可以先假设没有这个限制，我们会怎么做？

new_nums = []
cur = None
for i in range(n):
    if cur == nums[i]:
        count += 1
 else:
        count = 1
        cur = nums[i]
    if count > 2:
        continue
    new_nums.append(nums[i])

由于有这个限制，所以我们要做的就是把new_nums这个数组去掉，其实去掉是很简单的，因为我们可以让nums这个数组自己覆盖自己。因为产出的数据的数量一定是小于等于数组长度的，所以不会出现数组越界的问题。我们只需要维护一个下标记录nums数组当中允许覆盖的位置即可。

这个也是非常常见的做法，我们在之前的题目当中也曾经见到过。

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # start是起始覆盖指针，指向第一个可以覆盖的位置
        start, cur, cnt = 0, None, 0
        n = len(nums)
        if n == 0:
            return 0
        for i in range(n):
            if cur == nums[i]:
                cnt += 1
            else:
                cnt = 1
                cur = nums[i]
            # 如果数量超过2，说明当前元素应该舍弃，则continue
            if cnt > 2:
                continue
            # 否则用当前元素覆盖start位置，并且start移动一位
            else:
                nums[start] = nums[i]
                start += 1
        return start

关于这段代码，还有一个简化版本，我们可以把cnt变量也省略掉。因为元素是有序的，我们可以直接用nums[i]和nums[i-2]进行判断，如果相等，那么说明重复的元素一定超过了两个，当前元素需要跳过。

简化之后的代码如下：

class Solution(object):
    def removeDuplicates(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        i = 0
        for n in nums:
            if i < 2 or n != nums[i - 2]:
                nums[i] = n
                i += 1
        return i

总结

今天的题目不难，总体来说算是Medium偏低难度，主要有两点值得称道。第一点是C++风格inplace变更数组的做法，第二点就是数组自我覆盖的方法。除此之外，题目几乎没什么难度，我想大家应该都能想出解法来。

如果喜欢本文，可以的话，请点个关注，给我一点鼓励，也方便获取更多文章。

本文始发于公众号：TechFlow