カラー分類

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

#ifndef C148_H
#define C148_H
#include
#include
using namespace std;
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 len = nums.size();
        if (len <= 0)
            return;
        int i = 0, j = len - 1;
        int k = 0;
        while (k < len&&k <= j)
        {
            if (nums[k] == 0)
            {
                if (k == i)
                    ++k;
                else
                    swap(nums[i], nums[k]);
                ++i;
            }
            else if (nums[k] == 2)
            {
                swap(nums[k], nums[j]);
                --j;
            }
            else
                ++k;
        }
    }
};
#endif