lintcode-排色II-143
782 ワード
k種の異なる色を含むn個のオブジェクトの配列を指定し、同じ色のオブジェクトを隣接させ、1,2,...kの順に並べ替える.
サンプル
colors=
に注意
コードライブラリのソート関数を使用してこの問題を解決することはできません.
に挑戦
かなり直接的な解決策は,カウントソートを用いて2パススキャンするアルゴリズムである.これによりO(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);
}
}
};