分類
發燒車訊

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

本文始發於個人公眾號:TechFlow,原創不易,求個關注

今天是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 排版

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】

USB CONNECTOR掌控什麼技術要點? 帶您認識其相關發展及效能

台北網頁設計公司這麼多該如何選擇?

※智慧手機時代的來臨,RWD網頁設計為架站首選

※評比南投搬家公司費用收費行情懶人包大公開

※幫你省時又省力,新北清潔一流服務好口碑

※回頭車貨運收費標準