lintcode-排色II-143

782 ワード

k種の異なる色を含むn個のオブジェクトの配列を指定し、同じ色のオブジェクトを隣接させ、1,2,...kの順に並べ替える.
サンプル
colors=[3, 2, 2, 1, 4]k=4を与えて、あなたのコードはその場で操作して配列を[1, 2, 2, 3, 4]にするべきです
に注意
コードライブラリのソート関数を使用してこの問題を解決することはできません.
に挑戦
かなり直接的な解決策は,カウントソートを用いて2パススキャンするアルゴリズムである.これによりO(k)の余分なスペースがかかります.余分なスペースを使わずに完成できますか?
解題の構想:速い列の中で配列の区分の思想を運用します
class Solution{
public:
      
    int solve(vector &v,int begin,int end,int color){  
        int slow=begin-1,fast=begin;  
        while(fast &colors, int k) {
        int begin=0,end=colors.size();
        
        for(int i=1;i<=k;++i){
            begin=solve(colors,begin,end,i);
        }
    }
};