LeetCode 80，不使用外部空間的情況下對有序數組去重

今天是LeetCode專題的第49篇文章，我們一起來看LeetCode的第80題，有序數組去重II(Remove Duplicates from Sorted Array II)。

這題的官方難度是Medium，通過率是43.3%，點贊1104，反對690。這題的通過率有一點點高，然後點贊比也不是很高。說明這題偏容易，並且大家的評價偏低。也的確如此，我個人覺得，大家評價不好的主要原因還是這題偏容易了一些。

題面

其實從題目的標題當中我們已經可以得到很多信息了，實際上也的確如此，這題的題面和標題八九不離十，需要我們對一個有序的數組進行去重。不過去重的條件是最多允許一個元素出現兩次，也就是要將多餘的元素去掉。並且題目還限制了需要我們在原數組進行操作，對於空間複雜度的要求是。由於我們去除了元素之後會帶來數組長度的變化，所以我們最後需要返回完成之後數組的長度。

這是一種常規的做法，在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變更數組的做法，第二點就是數組自我覆蓋的方法。除此之外，題目幾乎沒什麼難度，我想大家應該都能想出解法來。

如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。

本文使用 mdnice 排版