完整的问题是:



这个问题是从“破解编码面试”中挑选出来的,解决方案是这样的:



我的问题是,如果我们要缩小从中挑选随机数的数组,那么每个数字被挑选的概率为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在每个步骤都缩小。

当您以这种方式思考时,应该很容易看到该方法可以保证每个元素被选择的可能性相等。

09-10 11:27
查看更多