Leetcode題解 Python & C#：六月挑戰DAY11 Sort Colors

有三種顏色，編號為 0, 1, 2。給一個陣列包含三種顏色，要在 in-place 去由小至大排序過。

Note：不要使用內建的 sort() function。

題目給了兩種方向，先 Count 後排序，二是跑一遍就完成。方向一太簡單，數完各顏色再從頭依種類、數量做替換。

二被限制只能用常數空間，換句話說，只能記沒有長度的數值。

答案一定是 0 都在陣列的最左方， 2 都在陣列的最右方。如果 pass 一遍，遇 0 往左擺，遇 2 往右擺，這樣就能快速分類。

左方擺過 0 的位置就不再使用，同理右方擺過 2 的，如果重複用到，就會破壞已經排好的序列。

因此採用 「Two Pointer」 ，而 Two Pointer 也是一個 O(1) Space 的方法。

pass 過程遇到 0 或 2 都會使左界或右界縮窄，可以想成把答案夾出來。

Python

class Solution:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        l, m, r = 0, 0, len(nums)-1     
        while m <= r:
            if nums[m] == 0:
                nums[l], nums[m] = nums[m], nums[l]
                l += 1    
                m += 1
            elif nums[m] == 2:
                nums[r], nums[m] = nums[m], nums[r]
                r -= 1      
            else:
                m += 1

C#

public class Solution {
    public void SortColors(int[] nums) {
        int l = 0;
        int m = 0;
        int r = nums.Length-1;
        int tem = -1;
        while(m <= r)
        {
            if(nums[m] == 0)
            {
                tem = nums[l];
                nums[l] = 0;
                nums[m] = tem;
                l += 1;    
                m += 1;
            }
            else if(nums[m] == 2)
            {
                tem = nums[r];
                nums[r] = 2;
                nums[m] = tem;
                r -= 1;      
            }else
            {
                m += 1;
            }
        }        
    }
}