20.3 写一个函数,随机地从大小为n的数组中选取m个整数

题目

写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。

解答

这道题目和随机洗牌问题类似,只需要随机选取1个元素, 然后在剩下的元素里面随机选取下一个元素,不断这样操作即可。

这样做能保证每个元素选中的概率一样吗?也就是选中每个元素的概率都是1/n? 答案是YES,让我们来做一下简单的计算。

  • 选第1个元素:在n个中随机选,因此概率为1/n
  • 选第2个元素:在剩下的n-1个中随机选:1/(n-1),由于第1次没有选中它, 而是在另外n-1个中选:(n-1)/n,因此概率为:(n-1)/n * 1/(n-1) = 1/n
  • 选第3个元素:同上:(n-1)/n * (n-2)/(n-1) * 1/(n-2) = 1/n

。。。

因此,按照这种方法选取k个元素,每个元素都是以1/n的概率被选出来的。代码如下: 选出的m个数放到数组前m个位置。

 

文/Hawstein

0 Likes

你目前的身份是游客,评论请输入昵称和电邮!