6

私のインタビューの 1 つで、インタビュアーは私に尋ねました - あるサイズの配列には、赤、青、緑のボールがすべてランダムに混ざり合っています。RGBBBRRGGG のように、RGB は赤、緑、青を表します。

RRRRGGGGBBBB のような配列、つまり、すべての R、すべての G、およびすべての B を一緒にする最適な方法は何ですか。

赤、青、緑のすべてを ASCII 値に変換してから、最も効率的な並べ替えアルゴリズムを実行することを提案しました。しかし、彼は感銘を受けませんでした。この問題に対する他のより効率的な解決策はありますか? 最小の空間と時間の複雑さで?

4

7 に答える 7

15

配列を調べて、 、 、 の出現回数RをGそれぞれ数えるだけBです。次に、文字列を出力します。線形時間。

于 2012-08-11T06:31:30.240 に答える
9

インタビュアーは、あなたがオランダの国旗問題に詳しいかどうか知りたがっていたかもしれません。それは単純な線形解を持っています。ウィキペディアのページに例がありC++ます。Java

于 2012-08-11T08:05:25.160 に答える
0

この問題は、線形時間で簡単に実行できます。アルゴリズムをさらに改善するには、カウンター配列 int[3] を作成し、counter[0]、counter[1]、counter[2] に赤、緑、青をそれぞれカウントさせることができます。したがって、配列を一度だけ通過する必要があります。

スペースの複雑さを最小限に抑えるもう 1 つの解決策は、current、rg、gb の 3 つのポインターを使用することです。現在のポインターは、現在見ている配列の位置を示し、rg と gb はそれぞれ赤/緑と緑/青の境界です。current = 0、rg = -1、gb = n を初期化します。ここで、n = A のサイズです。

gb>current の間 - A[i] == R の場合、rg を右に 1 シフトし、current を rg に置き換えます。そうでない場合、A[i] == blue の場合、fb を左に 1 シフトし、current を gb に置き換えます。 - そうでなければ、何もしない

追加の配列を使用していないため、スペースの複雑さ = O(n) 時間の複雑さ = O(n)、各要素は最大 1 回交換されます

于 2015-03-11T19:14:33.557 に答える
0

編集私はあなたの質問を誤解したかもしれません

RGB 値を HSL 値に変換する必要があります。次に、最も近い色を教えてくれる色相がわかります。これにより、それが属する R/G/B セクションが分類されます。次に、色相、彩度、および照明を取り入れて、正確な順序を決定することができます。配列全体に対して、相互に。

于 2012-08-11T06:33:22.213 に答える
0

また、その「4R4G4B」のようにセーブできれば効率よくセーブできるかもしれません

于 2012-08-11T06:33:53.127 に答える