完整的问题是:
这个问题是从“破解编码面试”中挑选出来的,解决方案是这样的:
我的问题是,如果我们要缩小从中挑选随机数的数组,那么每个数字被挑选的概率为1/remaining_num_elements
。它如何在所有要素上保持平等?
最佳答案
想一想,就像您从一包m
数字中挑选n
随机数一样,第一个j
元素代表the numbers in your hand
,其余元素代表the numbers still in the bag
。 (正如您的书所建议的,您将j
从0迭代到m - 1
以提取数字。j
表示您已经从袋子中取出的整数的数量。)
如果您是从现实生活中的袋子中挑出m
整数,那么每次选择一个新数字时,您只会从袋子中拿走而不是从手中拿走。因此,remaining_num_elements
在每个步骤都缩小。
当您以这种方式思考时,应该很容易看到该方法可以保证每个元素被选择的可能性相等。