0

私はいくつかのアルゴリズムの割り当てに取り組んでおり、次のように求められました: O(n) の配列を要素 'r' または 'w' で並べ替えて、'r' が常に 'w' の前に来るようにしてください。したがって、入力が [w,r,w,r,w,r,w,w] のように見える場合、アルゴリズムの実行後、配列は [r,r,r,w,w,w,w,w] のようになります.

概念的には、これはすぐに非常に明確に思えました。最初の 'w' 要素の位置と最後の 'r' 要素の位置を保持する 2 つの境界変数を使用する必要がありました。

私のコードは次のようになります。

char[] A = new char[] { 'w', 'r', 'w', 'r', 'w', 'r', 'w', 'w' };

int lastRedPosition = A.Length - 1;
int firstWhitePosition = 0;

for (int i = firstWhitePosition ; i < A.Length; i++)
{
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position
    for (int j = lastRedPosition; j > firstWhitePosition; j--)
    {
        if (A[j] == 'r')
        {
            lastRedPosition = j;
            break;
        }
    }

    for (int k = firstWhitePosition; k < lastRedPosition; k++)
    {
        if (A[k] == 'w')
        {
            firstWhitePosition = k;
            break;
        }
    }

    A[firstWhitePosition] = 'r';
    A[lastRedPosition] = 'w';
}

ネストされた for ループにもかかわらず、直感的に O(n) で実行されると思います。これは、全体として、配列が 1 回だけトラバースされるためです。lastRedPosition 変数と firstWhitePosition 変数を使用して、どこにいたかを追跡しているためです。

ただし、同じネストされたforループのため、これをより正式に動機付けるのは難しいと思います...誰かが正しいdirectopmへのポインタを教えてもらえますか?

4

6 に答える 6

4

これはクイックソートのイテレーション 1 にすぎませんか?

「w」を押すまで左からスキャンします。次に、「r」を押すまで右からスキャンします。次に、2 つの要素を交換して続行します。2 つのスキャナーが一緒になると停止します。

それが O(n) です。

編集: など:

int i = 0, j = n-1;
while(true){
  while(a[i]=='r' && i<n) i++;
  while(a[j]=='w' && j>0) j--;
  if (i >= j) break;
  swap(a[i], a[j]);
}
于 2013-01-07T19:27:39.400 に答える
2

最初の問題は、アルゴリズムが正しくないことです。'w'配列に s のみまたはsのみがある場合でも、外側のループの最後でaと an の'r'両方を配列に書き込みます。'w''r'

その場合、コードには実際にΘ(N²)時間がかかります。すべてが次のとおりであるとしましょう'r':

char[] A = new char[] { 'r', 'r', 'r', 'r', 'r', 'r', 'r', 'r' };

int lastRedPosition = A.Length - 1;
int firstWhitePosition = 0;

for (int i = firstWhitePosition ; i < A.Length; i++)
{
    // determine the first red from the right e.g. the lastred, ending at the firstwhite position
    for (int j = lastRedPosition; j > firstWhitePosition; j--)
    {
        if (A[j] == 'r')
        {
            lastRedPosition = j;
            break;
        }
    }

jA.length - 1 - i今です。最初の繰り返しでは、'r'すぐにi 'w's が配列の最後のエントリに書き込まれlastRedPosition、これらの最初のエントリのインデックスであることがexcept for the first iteration,わかりました。

    for (int k = firstWhitePosition; k < lastRedPosition; k++)
    {
        if (A[k] == 'w')
        {
            firstWhitePosition = k;
            break;
        }
    }

firstWhitePositionは常に0kです。_ したがって、インクリメントされた回数です。lastRedPosition'w'firstWhitePosition kA.length - 1 - i

の増分の合計iを合計します。~N²/2k

    A[firstWhitePosition] = 'r';
    A[lastRedPosition] = 'w';
}

A[firstWhitePosition]が実際に で'w'あり、A[lastRedPosition]実際に であるかどうかを確認する必要があり'r'ます。そうでない場合は、完了です。そして、外側のループは をチェックする必要がありますfirstWhitePosition < lastRedPosition。

于 2013-01-07T20:09:24.677 に答える
1

配列全体が 1 回だけトラバースされるからといって、自動的に O(n) になるわけではありません。実際には、最も最適でないケース (big-O の定義) では、配列全体が実際に 2 回走査され、2 回目の走査は外側のループ内で発生し、O(n^2) になります。

配列に r と w のみが含まれることを保証できる場合、O(n) アプローチは、配列を 1 回調べて、r と w の数を数えてから、自分で配列を再構築することです。これは実際には 2 回の走査で O(2n) になりますが、従来はこれらの係数は削除されていました。

于 2013-01-07T19:00:14.153 に答える
1

while外側のループを、実行されるまで実行されるループに変換するfirstWhitePositionと、見やすくなりますlastRedPosition。2 つの変数が一緒に配列を 1 回トラバースするだけであることは明らかです。

于 2013-01-07T19:00:36.457 に答える
0

技術的には、これは O(N) です。ただし、パフォーマンスの観点からは O(2N) であり、平均的なケースでは可能な限り半分の速さです。これは、外側のループが要素ごとに 1 回実行され、それらの間の内側のループがすべての要素をトラバースするためです。つまり、要素の 2 倍の反復があります。

あなたの考えは正しいですが、外側のループがすべての要素をトラバースする代わりに、すべてrの がすべての の左側にあることを「知った」とたんに停止した場合はどうなるwでしょうか?

別の言い方をすれば、配列の右端からr(左側に配置する必要がある) をスキャンし、左側から (右側に配置する必要があります) をスキャンすることから始めますw。wが の左側にある場合はw、それらを交換して続行する必要があります。ただし、「最後の r」インデックスが「最初の w」インデックスの左側にある場合は、完了であり、関数全体を終了する必要があります。代わりに、現在の実装はループ (およびスワッピング) を続けます。これが非効率です。ヘンリーが示唆するように、外側の for ループを while ループに置き換えます。終了条件は、最後のループがr最初のループの左側にあることwです。

于 2013-01-07T19:03:42.467 に答える
0

  1. 配列を 1 回調べて、「r」と「w」の数を数え、numberR と numberW として格納します。「r」および「w」以外の文字を S2 という StringBuffer に格納します。

  2. numberR 'r's を新しい StringBuffer S1 に出力します。S2 を S1 に追加します。W 個の 'w' を S1 に追加します。

  3. StringBuffer から文字配列を取得します。

総コスト: O(n)

于 2013-01-08T22:03:54.250 に答える