1

この質問は主に、カードのパックをシャッフルするという有名なインタビューの質問に関連しています。私はSOをさまよって、同様の質問を見つけましたが、答えはほとんどマークに達していないか、無視されています。

与えられた質問は、カードのパックをシャッフルする機能を構築することでした。

私の解決策：これは、リンクリスト内のすべてのカードを任意の順序で配置した場合に可能です（たとえば、並べ替えまたは並べ替えなし-順序は関係ありません）。乱数を生成し、そのmodを現在のカードの総数に変更し、リンクリストからそのインデックスを削除して、カードをshuffledArrayに格納します。

このソリューションは素晴らしいと思います。実行時間は次のとおりです。リンクリストを任意の順序で作成するためのO（n）。リンクリストから削除するためのO（n）。毎回乱数を生成するためのO（1）。

したがって、多かれ少なかれ、このアルゴリズムのO（n）の下限があります。

気になるのは空間です。現在使用されているスペースは次のとおりです。1）リンクリストの場合はO（n）2）shuffledArrayの場合はO（n）。

ここでも、O（n）の下限です。

これはその場で行うことができますか？つまり、このn個の余分なスペースを使用しないということです。O（n）未満の時間で実行できますか？

4

3 に答える 3

3

フィッシャー-イェーツシャッフルはインプレースで機能し、正確にn-1個の乱数を生成します。

于 2012-06-02T19:04:05.323 に答える
0 
void shuffle(vector<T> v)
{
    int n = v.size();
    for (int i = 0; i < n; i++)
        swap(v[i], v[i+rand(n-i)]);
};

帰納法による証明：

  1. 単一の要素ベクトルは自明にソートされます
  2. 最初の要素はランダムに選択され、誘導によってベクトルの残りの部分がシャッフルされます
于 2012-06-02T19:04:03.140 に答える
-1

カードを繰り返してみませんか。各ステップで、1〜52の乱数を生成し、現在のカードをこの乱数のカードと交換しますか？

あれについてどう思う？

于 2012-06-02T19:08:52.303 に答える