Leetcode典型題解答和分析、歸納和彙總——T75（顔色分類）

題目描述：

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

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

題目解析：

本題可以直接計算出數組中0，1，2的數字個數，然後再進行排列組合。但題目要求我們使用常數空間的一趟掃描算法，于是我們采用“三路歸并”的荷蘭旗問題解決方案。

具體為：設定三個指針，分别為p0,cur,p2,分别用來指向0值元素，目前元素，2值元素。首先令p0指向數組第一個元素，p2指向最後一個元素，然後分别計算nums[cur]的值，如果nums[cur]==0,則 和nums[p0]進行交換，并且p0++，cur++，如果nums[cur]==2 則和nums[p2]的值進行交換，p2--，其餘情況則cur++

具體代碼實作：

class Solution{
    public:
    void sortColors(vector<int>& nums)
    {
        int p0=-1, cur = 0, p2 = nums.size();
        while(cur<p2)
        {
            if(nums[cur]==0)
            swap(nums[++p0],nums[cur++]);

            else if(nums[cur]==1)
            cur++;
            
            else 
            swap(nums[cur],nums[--p2]);
        }
    }
};