algorithm - リンクリストから1つの要素をランダムに選択するアルゴリズムを設計する

Question

重複の可能性：
長さが不明なリンクリスト内の均一なランダム要素をどのように選択しますか？

リンクリストから要素をランダムに選択したいが、リンクリストの長さがわからないとします。

要素をランダムに選択するために、実行時間をできるだけ短くするアルゴリズムを設計します。

Answer 1

を使用した単純なアルゴリズムがありO(N)、長さを取得してから要素を選択します。

しかし、すべての要素に 1 回だけアクセスするオンライン アルゴリズムを使用すると、より適切に実行できます。

最初の要素を答えとして選択し、次にk番目の要素で答えをその要素に置き換える確率は1/kです。この方法に偏りがないことは、数学的帰納法で証明できます。

一般化されたバージョン (k 個の要素を選択) は、リザーバー サンプリングです。

Answer 2

これを考慮してください：リンクされたリストに含まれるアイテムの数を追跡する変数があると仮定しています（標準プログラミングプラクティス）。その変数を渡す関数がある場合は、リンクされたリスト内のアイテムへのポインターを用意し、ポインターを rand() % Amount_Of_Items に設定し、使用する必要がある場合は関数にポインターを返すようにするだけです。それ。