LeetCode 75 顔色分類（荷蘭國旗問題，三數排序）

題目描述

給定一個包含紅色、白色和藍色，一共 n 個元素的數組，原地對它們進行排序，使得相同顔色的元素相鄰，并按照紅色、白色、藍色順序排列。此題中，我們使用整數 0、 1 和 2 分别表示紅色、白色和藍色。

示例 1：

輸入：nums = [2,0,2,1,1,0]

輸出：[0,0,1,1,2,2]

示例 2：

輸入：nums = [2,0,1]

輸出：[0,1,2]

示例 3：

輸入：nums = [0]

輸出：[0]

示例 4：

輸入：nums = [1]

輸出：[1]

題解

數軸上，起始位置 i=0,j=0,k=n-1,三數排序要保證的是[0,j-1] 區間内的數是0，[j,i-1] 區間是1，[k,n-1] 區間是2。排序的過程如下：

• 如果nums[i]==0,就需要就将 i 指針所指向的數與 j 指針所指向的數交換，且由于交換過去了，j 已經是滿足等于0的位置了，是以j++，i++
• 如果nums[i]==1，那麼i++即可，要滿足[j,i-1] 區間，是以i++
• 如果nums[i]==2，需要将2位置交換到k後面，是以k–，i 沒有變化是因為交換過去的數字不确定是1還是0。

class Solution {
public:
    void sortColors(vector<int>& nums) {
        for(int i=0,j=0,k=nums.size()-1;i<=k;)
        {
            if(nums[i]==0) swap(nums[i++],nums[j++]);
            else if(nums[i]==2) swap(nums[i],nums[k--]);
            else if(nums[i]==1) i++;
        }
    }
};