荷蘭三色旗

leetcode 75 顔色分類

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顔色的元素相鄰，并按照紅色、白色、藍色順序排列。

此題中，我們使用整數 0、 1 和 2 分别表示紅色、白色和藍色

           

示例

輸入: [2,0,2,1,1,0]
輸出: [0,0,1,1,2,2]
           

class Solution {
public:
    void sortColors(vector<int>& nums) {
        // 荷蘭三色旗
        int cur = 0, start = 0, end = nums.size()-1;
        while(cur <= end){
            if(nums[cur] == 0){
                swap(nums[cur], nums[start++]);
            }else if(nums[cur] == 2) {
                swap(nums[cur], nums[end--]);
                cur--;
            }
            cur++;
        }
    }
};