WEI-CHENG CHEN

描述

就是陣列要按照 red(0), white(1), blue(2)這樣去排列

要原地排

[排紅的(0)... , 排白的(1)..., 排藍的(2)...,]

解法：三指針法

建立三個指針，分別：

• low=0：用于放置 0
• mid=0：處理當前位置
• high=n-1：用于放置 2

接下的處裡邏輯，以 mid 為主：(當下第一眼我還以為是二分搜 XD，但她不是，就很單純的一筆直由前到後)

• 當nums[mid]==1時：表示他是白色 => 要在中間 => 不用理他
• 當nums[mid]==0時：表示他是紅色 => 要把它給指針 low 去管理 => num[low]=num[mid] => low++
• 當nums[mid]==2時：表示他是藍色 => 要把它給指針 high 去管理 => num[high]=num[mid] => high--

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int low = 0;
        int mid = 0;
        int high = nums.size()-1;
        while(mid<=high){
            if(nums[mid]==1) mid++;
            else if(nums[mid]==0){
                swap(nums[low], nums[mid]);
                low++;
                mid++; // 換過來的 nums[mid] 還沒被處理過，你不能直接跳過它！
            }else{
                swap(nums[high], nums[mid]);
                high--;
                // mid++; // nums[high] 一定是左邊區域結束的下一位，已經處理過了 => 要往前
            }
        }
    }
};