3

私はインタビューでこの質問をされ、さまざまな解決策を示しましたが、インタビュアーは納得していませんでした。私は解決策を見つけることに興味があります。あなたの意見を投げてください：

Q：iPodにシャッフルを実装するための効率的なデータ構造を記述してください。すべての曲を再生する必要があります。毎回異なるランダムな順序で、同じ曲を繰り返さないでください。（主にO（n））

1つの解決策は、インタビューの後で考えました。再帰なしでランダム化されたクイックソートを実行できます。ランダムに、1つのピボットO（1）を選択してから、クイックソートO（n）を実行します。これで曲が順番に並べ替えられ、最後まで再生します。それが終わりに達したら、私は再びランダムなピボットを選択し、このプロセスを何度も繰り返します。

よろしく、セトゥー

4

6 に答える 6

8

フィッシャー-イェーツシャッフルが必要です。現在受け入れられている回答は1つに反するため、そのページに記載されている実装エラーに注意してください。

于 2010-10-31T20:08:35.840 に答える
5

すべての曲を配列に配置します...配列内の要素ごとに、ランダムな位置に交換します。

于 2010-10-29T15:58:17.720 に答える
1

さて、頭に浮かぶ最初の線形時間ソリューション：

すべての曲のリンクリストを作成できます。これには約O（n）かかります（挿入が定数時間の操作である場合）。次に、乱数を生成し、リストのサイズを法として乱数インデックスを取得し、そのインデックスを削除して新しいリストに追加します（どちらも定数時間演算です）。

各O（n）の挿入+各O（n）の削除+ 2番目の挿入O（n）。これは全体として線形時間ソリューションにつながります。

編集：私はリストを歩くことを完全に忘れました。したがって、代わりに、結果を固定長の配列にすることができます。リンクリストの先頭をポップし、それにランダムインデックスを割り当てて、配列にデータを入力します。

于 2010-10-29T16:03:07.890 に答える
1

ネイト（編集済み）とブライアンのアルゴリズムはフィッシャー-イェーツシャッフルO（n）であり、並べ替えによるシャッフルはO（nlogn）ですが、実際にはより高速な場合があります（http://en.wikipedia.org/wiki/Fisher% E2％80％93Yates_shuffle＃Comparison_with_other_shuffling_algorithms）。曲のシャッフルを間違えると、取るに足らない結果になる可能性がありますが、オンラインポーカーゲームのシャッフルアルゴリズムを作成している場合は、自分が何をしているのかを確認してください（http://www.cigital.com/news/index.php?pg= art＆artid = 20）。

于 2010-10-29T20:08:38.703 に答える
1

あなたが欲しいのはフィッシャー-イェーツシャッフルです。これがJavaでの実装です：

public void shuffle(Song[] songs) {
    Random r = new Random();
    for(int i = 0; i < songs.length - 1; i++) {
        int swap = i + r.nextInt(songs.length-1-i);
        T temp = songs[i];
        songs[i] = songs[swap];
        songs[swap] = temp;
    }
}
/* r.nextInt(max) returns integer 0 to max-1 inclusive */

それがどのように機能するかは、配列全体を帽子として扱い、ランダムな要素を引き出して配列の前面に並べ始めます。後のすべての要素iは「バケット内」にあり、前のすべての要素iはシャッフルされます。

于 2018-05-16T01:33:24.047 に答える
0

私は初心者です。頭に浮かぶ解決策を言わせてください。何か問題があれば教えてください。

曲が単一または二重にリンクされたリストに保存されていると仮定しましょう。音楽プレーヤーが開かれるたびに、（任意の数）未満の乱数を選択してkを想定し、リスト内のk個のノードごとに逆にします。同様に2回または最大3回（必要に応じて）実行すると、O（シャッフルする2n）またはO（3n）時間。最後に、リストの最後のノードへのポインターがあります。そして、曲が聴かれる（ノードが訪問される）たびに、ノードを削除し、O（1）時間で実行できる最後のノードの隣に挿入します。これは、音楽プレーヤーが閉じられるまで続きます。

答えの正しさを知りたがっています。

于 2014-12-20T12:30:11.133 に答える