從列表中原位刪除部分元素的正確方法

（圖文無關）

這是一篇面向編程初學者的文章。看到 挑戰自己|LeetCode 刷題開胃菜 - 知乎專欄，我覺得有必要講一下這幾道LeetCode的正確做法。

簡單來說，原題中共同的要求是給定一個數組（Python列表），在不構建新的數組的情況下，移除數組中某些符合條件的元素。比如說，數組[1,2,3,1,3,4]，移除所有的1之後，就變成了[2,3,3,4]。可以注意到，列表在移除某些元素之後，長度會變短，元素的下標會做相應的調整。如果是世界最好的語言PHP，它的數組其實是數字做key的hashmap，那麼只要刪掉相應的key，然後用array_merge重整一下就行了（當然，這種做法完全不符合題意的in place）；但對Python來說，它的list是真正的順序表，需要仔細考慮刪除的過程。我知道大家都喜歡[x for x in array if ...]，但是題意是要用原始列表，那麼就應該按題目要求。

為了簡單，我們首先將問題簡化一下：我們有一個列表，其中某些元素是None，現在我們要操作這個列表使其中僅有非None的元素留下來。顯然，其他問題可以通過先將要刪除的元素設置為None（就像javascript裡面的delete a[index]那樣，在數組裡留個洞），然後調用這個過程來實現。

當然，最直接的方法，我們可以選擇循環調用remove(None)，直到拋出異常。不過這種做法相對於其他語言來說太過於作弊了，而且性能上也不是最好的（後面會分析），暫時不提。

一種常見的錯誤做法是這樣的：

a = [1, 1, None, None, 3, 3, 4, 4]nfor i in range(0, len(a)):n if i >= len(a):n breakn if a[i] is None:n del a[i]n

運行會發現得到的結果是不正確的，有一個None沒有刪掉。為什麼呢？程序中遇到i = 2的時候，調用del a[2]，會將後面的元素前移一位，于是之間下標為3的元素會變成下標為2的元素，而下一次處理的是i = 3，於是就漏掉了一個元素。

由於刪除一個元素的時候，這個元素後面的元素下標都會改變，一種簡單的想法就是反過來從後向前刪除：

a = [1, 1, None, None, 3, 3, 4, 4]nfor i in range(len(a) - 1, -1, -1):n if a[i] is None:n del a[i]n

這種做法是正確的。但是，如果數組很大，這種做法會比較慢。原因在於，刪除一個元素的時候，會重新複製這之後所有的元素，這個過程需要的時間跟數組長度成正比，這樣最壞情況下，這個程序就需要O(n^2)的時間來完成這個過程（想像一個1和None間隔的數組）。O(f(n))這個符號表示漸進複雜度，當問題規模用n來表示（對這個問題來說，就是數組長度為n）時，需要消耗的時間的增長速度的上界不超過f(n)的某個較大的倍數。

我們希望對於長度為n的數組，只使用O(n)的操作來完成這個過程。實際上，相應的代碼是很簡單的：

j = 0nfor i in range(0, len(a)):n if a[i] is not None:n a[j] = a[i]n j += 1ndel a[j:]n

解釋下原理，我們考慮去掉None元素的這個過程，它的原理在於將非None的元素從原來的位置上，調整到更靠前的位置上。在這個過程中，元素的下標一定不會增加，而是會不變或者減少。因此我們讀取的下一個元素一定還沒有被修改過，那麼我們用i來表示準備移動的元素的下標，用j來表示下一個要放入的下標位置，就寫出了上面的代碼。

再來考慮最初的問題，我們要移除數組中某些符合條件的數，當然沒有必要真的將它設置為None，只需要在讀取的過程中，一邊讀取一邊判斷就好了：

def filter_in_place(array, filter_):n j = 0n for i in range(0, len(array)):n if filter_(array[i]):n array[j] = array[i]n j += 1n del array[j:]n return len(array)n

刪除某個值的元素就可以寫成：

def remove_in_place(array, num):n filter_in_place(array, lambda x: x == num)n

刪除重複元素稍微複雜些，要點在於列表已經排好了序這件事。可以構造一個閉包來完成這件事：

last_num = Nonendef filter_duplicate(x):n nonlocal last_numn if x == last_num:n return Falsen else:n last_num = xn return Truenndef remove_duplicate_in_place(array):n return filter_in_place(array, filter_duplicate)n

如果Python2的話可以用一個可變對象來代替nonlocal：

last_num = [None]ndef filter_duplicate(x):n if x == last_num[0]:n return Falsen else:n last_num[0] = xn return Truenndef remove_duplicate_in_place(array):n return filter_in_place(array, filter_duplicate)n

用一個類也是一樣的：

class DuplicatedFilter(object):n def __init__(self):n self.last_num = Nonenn def __call__(self, x):n if x == self.last_num:n return Falsen else:n self.last_num = xn return Truenndef remove_duplicate_in_place(array):n return filter_in_place(array, DuplicatedFilter())n

那最後，要保留兩個，也很簡單了：

class DuplicatedFilter(object):n def __init__(self):n self.last_num = Nonen self.count = 0nn def __call__(self, x):n if x == self.last_num:n if self.count >= 1:n return Falsen else:n self.count += 1n return Truen else:n self.last_num = xn self.count = 0n return Truenndef remove_duplicate_in_place(array):n return filter_in_place(array, DuplicatedFilter())n

請自行寫出閉包的版本作為課後練習。