0

数字の連続したストリームが入ってきます。それらすべてを保存するスペースがありません。ただし、いつでも同じ確率で任意の数を選択できるメカニズムを考案してください。

4

1 に答える 1

7

1 つの数値のスペースを確保し、n 番目の数値を 1/n の確率でその数値に置き換えます。

http://en.wikipedia.org/wiki/Reservoir_sampling

于 2012-10-08T04:42:57.377 に答える