148. 顏色分類

給定一個包含紅，白，藍且長度為 n 的數組，將數組元素進行分類使相同顏色的元素相鄰，并按照紅、白、藍的順序進行排序。

我們可以使用整數 0，1 和 2 分別代表紅，白，藍。

?注意事項

不能使用代碼庫中的排序函數來解決這個問題。
排序需要在原數組中進行。

樣例

給你數組?[1, 0, 1, 2], 需要將該數組原地排序為?[0, 1, 1, 2]。

挑戰?

一個相當直接的解決方案是使用計數排序掃描2遍的算法。

首先，迭代數組計算 0,1,2 出現的次數，然后依次用 0,1,2 出現的次數去覆蓋數組。

你否能想出一個僅使用常數級額外空間復雜度且只掃描遍歷一遍數組的算法？

?

?

?

比較容易聯想到快排，把所有0扔到1左邊，把所有2扔到1右邊，問題就在于我們怎樣找扔的位置

因為我們不知道1在哪，所以把0扔到最左（left），2扔到最右（right），初始化left=0，right=size()-1

2比較好處理，查到一個2就往最后right扔，扔一次就right--

那么怎么找0該扔到的位置？

有這么幾種情況

1、i=left，就是說查到的0就在該在的位置，那么這時候需要i++,left++

2、i!=left，那么這時候就需要交換，交換后left位置為0，所以需要left++

void sortColors(vector<int> &nums) {
        // write your code here
        int left=0, right=nums.size()-1;
        int index=0;
        while(index<=right){
            if(nums[index]==0){
                if(index==left){
                    index++;
                }
                else{
                    swap(nums[index], nums[left]);
                }
                left++;
            }
            else if(nums[index]==2){
                swap(nums[index], nums[right]);
                right--;
            }
            else{
                index++;
            }
        }
    }

看的出來，查到1就直接跳過了，只處理查到0和2的情況