本文始發於個人公眾號：TechFlow，原創不易，求個關注
今天是LeetCode專題的44篇文章，我們一起來看下LeetCode的75題，顏色排序 Sort Colors。
這題的官方難度是Medium，通過率是45%，點贊2955，反對209（國際版數據），從這份數據上我們大概能看得出來，這題的難度不大，並且點贊遠遠高於反對，說明題目的質量很不錯。事實上也的確如此，這題足夠簡單也足夠有趣，值得一做。
題意
給定一個n個元素的數組，數組當中的每一個元素表示一個顏色。一共有紅白藍三種顏色，分別用0，1和2來表示。要求將這些顏色按照大小進行排序，返回排序之後的結果。
要求不能調用排序庫sort來解決問題。
桶排序
看完題目應該感受到了，如果沒有不能使用sort的限制，這題毫無難度。即使加上了限制難度也不大，我們既然不能調用sort，難道還不能自己寫個sort嗎？Python寫個快排也才幾行而已。
自己寫sort當然是可以的，顯然這是下下策。因為元素只有3個值，互相之間的大小關係也就只有那麼幾種，排序完全沒有必要。比較容易想到，我們可以統計一下這三個數值出現的次數，幾個0幾個1幾個2，我們再把這些數拼在一起，還原之前的數據不就可以了嗎？
這樣的確可行，但實際上這也是一種排序方案，叫做基數排序，也稱為桶排序，還有些地方稱為小學生排序（大概是小學生都能懂的意思吧）。基數排序的思想非常簡單，我們創建一個數組，用它的每一位來表示某個元素是否在原數組當中出現過。出現過則+1，沒出現過則一直是0。我們標記完原數組之後，再遍歷一遍標記的數組，由於下標天然有序，所以我們就可以得到排序之後的結果了。
如果你還有些迷糊也沒有關係，我們把代碼寫出來就明白了，由於這題讓我們提供一個inplace的方法，所以我們在最後的時候需要對nums當中的元素重新賦值。
class Solution:
def sortColors(self, nums: List[int]) -> None:
""" Do not return anything, modify nums in-place instead. """
bucket = [0 for _ in range(3)]
for i in nums:
bucket[i] += 1
ret = []
for i in range(3):
ret += [i] * bucket[i]
nums[:] = ret[:]
和排序相比，我們只是遍歷了兩次數據，第一次是遍歷了原數組獲得了其中0，1和2的數量，第二次是將獲得的數據重新填充回原數組當中。相比於快排或者是其他一些排序算法的耗時，桶排序只遍歷了兩次數組，明顯要快得多。但遺憾的是這並不是最佳的方法，題目當中明確說了，還有隻需要遍歷一次原數組的方法。
two pointers
在我們介紹具體的算法之前，我們先來分析一下問題。既然顏色只有三種，那麼當我們排完序之後，整個數組會被分成三個部分，頭部是0，中間是1，尾部是2。
我們可以用一個區間來收縮1的範圍，假設我們當前區間的首尾元素分別是l和r。當我們讀到0的時候，我們就將它和l交換，然後將l向後移動一位。當我們讀到2的時候，則將它和r進行交換，將r向左移動一位。也就是說我們保證l和r之間的元素只有1。
我們之前曾經介紹過這種維護一個區間的做法，雖然都是維護了一個區間，但是操作上是有一些區別的。之前介紹的two pointers算法，也叫做尺取法，本質上是通過移動區間的右側邊界來容納新的元素，通過移動左邊界彈出數據的方式來維護區間內所有元素的合法性。而當前的做法中，一開始獲得的就是一個非法的區間，我們通過元素的遍歷以及區間的移動，最後讓它變得合法。兩者的思路上有一些細微的差別，但形式是一樣的，就是通過移動左右兩側的邊界來維護或者是達到合法。
class Solution:
def sortColors(self, nums: List[int]) -> None:
""" Do not return anything, modify nums in-place instead. """
l, r = 0, len(nums)-1
i = 0
while i < len(nums):
if i > r:
break
# 如果遇到0，則和左邊交換
if nums[i] == 0:
nums[l], nums[i] = nums[i], nums[l]
l += 1
# 如果遇到2，則和右邊交換
# 交換之後i需要-1，因為可能換來一個0
elif nums[i] == 2:
nums[r], nums[i] = nums[i], nums[r]
r -= 1
continue
i += 1
這種方法我們雖然只遍歷了數組一次，但是由於交換的次數過多，整體運行的速度比上面的方法還要慢。所以遍歷兩次數組並不一定就比只遍歷一次要差，畢竟兩者都是的算法，相差的只是一個常數。遍歷的次數只是構成常數的部分之一。
除了這個方法之外，我們還有其他維護區間的方法。
維護區間
接下來要說的方法非常巧妙，我個人覺得甚至要比上面的方法還有巧妙。
我們來假想一下這麼一個場景，假設我們不是在原數組上操作數據，而是從其中讀出數據放到新的數組當中。我們先不去想應該怎麼擺放這個問題，我們就來假設我們原數組當中的數據已經放好了若干個，那麼這個時候的新數組會是什麼樣？顯然，應該是排好序的，前面若干個0，中間若干個1，最後若干個2。
那麼問題來了，假設這個時候我們讀到一個0，那麼應該怎麼放呢？為了簡化敘述我們把它畫成圖：
我們假設藍色部分是0，綠色部分是1，粉色部分是2。a是0最右側的下標，b是1部分最右側的下標，c是2部分最右側的下標。那麼這個時候，當我們需要放入一個0的時候，應該怎麼辦？
我們結合圖很容易想明白，我們需要把0放在a+1的位置，那麼我們需要把後面1和2的部分都往右側移動一格，讓出一格位置出來放0。我們移動數組顯然帶來的開銷會過於大，實際上沒有必要移動整個部分，只需要移動頭尾元素即可。比如1的部分左側被0佔掉了一格，那麼為了保持長度不變，右側也需要延伸一格。同理，2的部分右側也需要延伸一格。那麼整個操作用代碼來表示就是：nums[a+1] = 0，nums[b+1] = 1, nums[c+1] = 2。
假設我們讀入的數是1，那麼我們需要把b延長一個單位，但是這樣帶來的後果是2的部分被侵佔，所以需要將2也延長，補上被1侵佔的一個單位。如果讀到的是2，那麼直接延長2即可，因為2後面沒有其他顏色了。
假設我們有一個空白的數組，我們可以這麼操作，但其實我們沒有必要專門創建一個數組，我們完全可以用原數組自己填充自己。因為我們從原數組上讀取的數和擺放的數是一樣的，我們直接把数字擺放在原數組的頭部，佔用之前讀取的數即可。
光說可能還有些迷糊，看下代碼馬上就清楚了：
class Solution:
def sortColors(self, nums: List[int]) -> None:
""" Do not return anything, modify nums in-place instead. """
# 記錄0，1和2的末尾位置
zero, one, two = -1, -1, -1
n = len(nums)
for i in range(n):
# 如果擺放0
# 那麼1和2都往後平移一位，讓一個位置出來擺放0
if nums[i] == 0:
nums[two+1] = 2
nums[one+1] = 1
nums[zero+1] = 0
zero += 1
one += 1
two += 1
elif nums[i] == 1:
nums[two+1] = 2
nums[one+1] = 1
one += 1
two += 1
else:
nums[two+1] = 2
two += 1
總結
到這裏，這道題的解法基本上都講完了。
相信大家也都看出來了，從難度上來說這題真的不難，相信大家都能想出解法來，但是要想到最優解還是有些困難的。一方面需要我們對題目有非常深入的理解，一方面也需要大量的思考。這類題目沒有固定的解法，需要我們根據題目的要求以及實際情況自行設計解法，這也是最考驗思維能力以及算法設計能力的問題，比考察某個算法會不會的問題要有意思得多。
希望大家都能從這題當中獲得樂趣，如果喜歡本文，可以的話，請點個關注，給我一點鼓勵，也方便獲取更多文章。
本文使用 mdnice 排版
本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理
【其他文章推薦】
※為什麼 USB CONNECTOR 是電子產業重要的元件?
※網頁設計一頭霧水該從何著手呢? 台北網頁設計公司幫您輕鬆架站!
※台北網頁設計公司全省服務真心推薦
※想知道最厲害的網頁設計公司"嚨底家"!
※推薦評價好的iphone維修中心
※網頁設計最專業,超強功能平台可客製化
※別再煩惱如何寫文案,掌握八大原則!
