本文始發於個人公眾號：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網頁設計為架站首選
※評比南投搬家公司費用收費行情懶人包大公開
※幫你省時又省力,新北清潔一流服務好口碑
※回頭車貨運收費標準
近來積極拓展車用電池事業的南韓化學巨擘 LG Chem Ltd. 宣佈，該公司已敲定價值數億美元的電動車電池供應合約，對象是德國汽車製造商福斯 (Volkswagen AG) 旗下的豪華車廠奧迪 (Audi AG)。 LG Chem 目前為通用汽車 (General Motors Co.)、雷諾 (Renault SA)、福特汽車 (Ford Motor Co.)、現代汽車 (Hyundai Motor Co.) 以及起亞汽車 (Kia Motors Corp.) 等 20 家業者的車用電池供應商。日前 LG Chem 才宣布將與通用汽車等汽車廠商攜手研發一款車用電池，其單次充電的里程數多達 200 英里，為市面上大多數電動車的兩倍以上。 20 日 LG Chem 又傳出好消息，該公司透過聲明表示，會為奧迪的次世代插電式混合動力電動車提供車用電池，總值多達數百億韓圜，而由於奧迪與母公司福斯一起共用了許多汽車平台，因此 LG Chem 認為未來應該能與福斯敲定更多類似的協議。 （圖片來源：）
Saleen Automotive 在改車界享負盛名，無論任何車款經其改裝後，都會變得更快更有勁。最近他們看上了 Tesla 的 Model S 電動車，將其改裝為 Saleen FourSixteen，比起原版本擁有更高性能。 Saleen FourSixteen 採用與 Model S 相同的 416 匹引擎，不過其齒輪比率卻提高至 11.39:1，能大幅提高跑車的加速性能，因此由 0 加速至 100 公里只需 4 秒，比起 Model S 足足快了 1 秒。此外，Saleen FourSixteen 同時亦改善了冷卻系統及防傾桿，與及採用賽車用的車底盤及碳纖維剎車盤。 車廂內部也經過重新設計，將 Model S 原有的五座位改成全真皮的四座位，變成了一部真正的四座位超級電動跑車。該跑車目前已開放預訂，但售價並不便宜，約 15 萬 2 千美元。 （圖片來源：）
