0075. Sort Colors (Medium)

(當然，Medium的拍手也可以多拍幾下啦XD)

Question

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.

Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.

Note: You are not supposed to use the library’s sort function for this problem.

Example:

1
2

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up:

• A rather straight forward solution is a two-pass algorithm using counting sort.
  First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite the array with the total number of 0’s, then 1’s and followed by 2’s.
• Could you come up with a one-pass algorithm using only constant space?

分析/解題

給定一個陣列當中有n個物件，被著色成紅、白、藍，
請將其以in-place的方式將同顏色排序至相鄰，並順序亦為紅白藍。
這裡給定的陣列顏色紅/白/藍分別以0/1/2代表。

如果有印象的話，大家可能還記得之前有一題Move Zeroes，
差別在於這題是0, 1, 2，我們依舊可以用類似的概念來解題。

使用3個變數來分別記錄0/1/2的個數，
等到計完了，再依序覆寫到nums裡面，就可以得到答案，
這麼做會需要掃過陣列兩次，第一次用來計數，第二次用來填入新的値。

那麼，題目也問了：
有沒有辦法給出一個one-pass 的演算法來解此題呢？
(one-pass algorithm意思是指說只掃過整個資料一次，詳見wiki)

我們可以仿照先前的Two Pointer 的概念來思考。
首先，1在這個陣列當中是我們較不在意的部分，
因為它一定是排在整個陣列的中間，
然後左邊區塊最後會是0，右邊區塊最後會是2。

假設我們要排序，所要做的就是將0的部分都往左邊擺，
將2的部分都往右邊擺；最開始的時候，因為還沒排過，
我們可以將下一個要擺放的位置命名為i0和i2，
並假定應該要擺在0和n-1的位置。(陣列的最左邊和最右邊)
接下來，依序掃描整個陣列(假設迭代的index為i)，會有以下三個情況。

1. 碰到1:
   因為將0和2都擺完以後1自然在中間，所以完全不用管它XD

2. 碰到0:
   我們應該將其擺放在i0的位置 ，
   但原先i0所在的値不能平白消失，所以將其和i位置的値相交換。
   換完之後，i0 因為已經填入0了，
   故下個要填入0的位置必須更新 ，所以將i0遞增 。

3. 碰到2:
   同理，將其擺在i2的位置，和i位置的値相交換，再遞減i2 ；
   需要注意的是由於i的位置換到我們不知道值的部分 ，
   (前面碰到0的時候換的應該都是1，所以沒有影響)
   所以將i遞減，抵銷掉i在整個迴圈中每次加1的部分 ，
   以便迴圈的下一輪能檢查相同的位置。(檢查換過來的値 )

這整個迴圈的結束時間點應該在i和i2交錯的時候 ，
因為這代表後面都是2，既然後面已經相當於排完，
就可以結束整個迴圈了！

寫成程式碼如下，
幾個需要簡單注意的地方是，
當使用第一種方法 的時候，
其實可以直接開一個長度為3的陣列 來儲存數字出現次數；
其次，使用第二種方法 時，Python當需要判定條件會改變的狀 況時，
請使用while迴圈 ，因為for in range的寫法沒辦法動態地去改變條件。
(另外別忘記Python沒有++或 — ，請用+=和-=)

Java

Python

面試實際可能會遇到的問題

「時間/空間複雜度？」
(O(N)/O(1)，不論哪個解法，最多就是掃描過2次的nums的長度，
且我們基本上只會用到三個記錄各自數量的變數或三個索引值)

相似及延伸

1.0148. Sort List (Medium) 2.0324. Wiggle Sort II (Medium)

Special Thanks suggestions/corrections from viewers:
(歡迎提供意見協助更正歐~)

從LeetCode學演算法，我們下次見囉，掰~