lintcode-色分類-148

赤、白、青、長さnを含む配列を指定し、配列要素を同じ色の要素に隣接させ、赤、白、青の順に並べ替えます.
整数0,1,2を用いて,それぞれ赤,白,青を表すことができる.
サンプル
に注意
コードライブラリのソート関数を使用してこの問題を解決することはできません.
説明
かなり直接的な解決策は,カウントソートを用いて2パススキャンするアルゴリズムである.
まず,反復配列は0,1,2の出現回数を計算し,次いで配列を0,1,2の出現回数で順次上書きする.
定数レベルの余分な空間の複雑さだけを使用して配列を1回だけスキャンするアルゴリズムを考えられますか?
解題案:速い列の中で配列を区分する思想を運用する

class Solution{
public:
    
    int solve(vector<int> &v,int begin,int end,int color){
        int slow=begin-1,fast=begin;
        while(fast<end){
            if(v[fast]==color)
                swap(v[fast],v[++slow]);
            ++fast;    
        }
        return slow;
    }  
    void sortColors(vector<int> &nums) {
        solve(nums,solve(nums,0,nums.size(),0)+1,nums.size(),1);
    }
};