4

Skiena の Algorithm Design Manual を読んでいましたが、この問題を解決できませんでした。

配列 A が n 個の要素で構成され、それぞれが赤、白、または青であるとします。すべての赤がすべての青よりも前に来るように、すべての赤がすべての白よりも前に来るように、要素を並べ替えようとします。

Examine(A,i) { report the color of the ith element of A.
Swap(A,i,j) { swap the ith element of A with the jth element.

赤白青の並べ替えのための正確で効率的なアルゴリズムを見つけてください。線形時間ソリューションがあります。

クイックソートを使ってみたところ、ピボットが3つあれば解けるはずなのですが、クイックソートで重複が出てきたらどうしたらいいのかわかりません。

4

6 に答える 6

2

最初に 0 を指す赤いポインターと、配列の最後の要素を指す青いポインターの 2 つのポインターを維持します。

関数を使用して、配列を左から右にスキャンしExamineます。

  • 赤の要素に遭遇するたびに、(Swap関数を使用して) 現在の赤のポインターと交換し、赤のポインターをインクリメントします。
  • 同様に、青い要素に遭遇するたびに、それを現在の青いポインターと交換し、青いポインターを減らします。
  • 白い要素に遭遇すると、現在のポインターをインクリメントします。
  • 現在のポインターが青いポインターを横切ったときに停止します。

これで、配列は必要に応じて並べ替えられるはずです。

これがオランダ国旗問題です。

于 2013-03-03T15:09:23.933 に答える
1

これは実はオランダ国旗問題として知られる、ダイクストラが提唱した非常に有名な問題です。

上にリンクされたウィキペディアは、この問題やその他の問題にアプローチする方法についてかなりまともな説明を提供しています。

3 ウェイ クイック ソートは、このソールにも適用できます。このプレゼンテーションでは、その方法についてかなり良いアイデアが得られるはずです (関連コンテンツは 37 ページから始まります)。また、個別のキーの数は定数 3 であるため、O(n) でも機能します (43 ページで説明されているように)。

于 2013-03-03T15:08:46.377 に答える
0

非常に単純な線形時間アルゴリズムは次のとおりです。

  1. 配列を 1 回ループし、赤、白、青のカウントを rcount、wcount、bcount として見つけます。

  2. 0、rcount、(rcount + wcount) から始まる 3 つのカウンターを用意します。それらを rcounter、wcounter、および bcounter と呼びます。

  3. カウンターごとに、その範囲に適していない色になるまでインクリメントします

  4. 色に遭遇するたびに、0 から開始します。色が赤で (counter < rcount) の場合、rcount をインクリメントして続行します (範囲に応じて白と青の場合も同様) b. 色が白の場合は、wcounter と wcounter++ c. と交換します。色が青色の場合、bcounter と bcounter++ でスワップします

ループが終了すると、配列が作成されます。

于 2013-03-03T15:05:29.277 に答える
0

これは実際にはソートの問題ではありません。グループ分けの問題です。

赤、白、青の要素の数を数えながら、リストを反復処理します。これで、ソリューションの正確な構造がわかりました。たとえば、次のようになります。

XXXXYYYYZZZZZZZZZ

X は赤、Y は白、Z は青です。

ここで、3 つのポインターを作成します。1 つは X の開始位置、もう 1 つは Y の開始位置、もう 1 つは A の Z の開始位置です。

間違っているセット内の最初の要素になるまで、各ポインターを進めます。たとえば、これが A の場合:

XYXXXYYXYZZZZZZZZZ

私

X ポインターである I を 2 番目の位置 (インデックス 1) に進めます。これは、その要素が適切でないためです。

ポインターごとにこれを行うと、3 つのポインターのそれぞれが不適切な要素を指していることがわかります。次に、リストを繰り返し処理します。不適切な要素を見つけた場合は、対応するポインターと交換します。つまり、Y 内に X が見つかった場合は、それを Y ポインターと交換し、ポインター (Y) が何か不適切なものを指すようになるまでインクリメントします。また。

配列がソートされるまで続行します。

構造体を取得するためにリストを 1 回 (n ops) 反復処理し、各ポインターがリストを最大で 1 回反復処理するため (4 ポインター → 4n)、合計最大実行時間は 5n、つまり O(n) になります。

于 2013-03-03T15:10:54.947 に答える
-1

私はSkienaの本を読んでいて、この問題を見ました。

O（2n）で解決策を得ました：

A = [B,R,W,R,W,B] とします。

  1. 最初に配列を通過し、ピボット B を分割して、R または W であるすべての値が配列の先頭にプッシュされるようにします。

これで A は次のようになります。['R', 'W', 'R', 'W', 'B', 'B'] => O(n)

  1. 再び A を通過し、W をピボットして、R であるすべての値が配列の先頭にプッシュされるようにします。B は既に配置されているため、無視できます。

結果: ['R', 'R', 'W', 'W', 'B', 'B'] => O(2n)

これは線形ソリューションです。

これは正しい方法ですか？

于 2015-06-09T10:22:33.800 に答える