色の分類

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

class Solution{
public:
    /**
     * @param nums: A list of integer which is 0, 1 or 2 
     * @return: nothing
     */    
    void sortColors(vector<int> &nums) {
        // write your code here
        int n = nums.size();
        int left = 0;
        int right = n-1;
        int p = 0;
        while (p < n && left < right)
        {
            if (nums[p] == 0)
            {
                while (nums[left] == 0)
                {
                    left++;
                }
                if (p > left)
                {
                    swap(nums[left], nums[p]);
                }
                else    
                {
                    p = left + 1;
                }
            }
            else if (nums[p] == 2)
            {
                while (nums[right] == 2)
                {
                    right--;
                }
                if (p < right)
                {
                    swap(nums[right], nums[p]);
                }
                else
                {
                    break;
                }
            }
            else
            {
                p++;
            }
        }
    }
};