从M个数中随机取出N个

简介:

看到这样一个题目:在M个数中,随机取出其中的N个,要求等概率。

这应该是一个比较简单的题目,看到题目后的第一想法是:维护一个关于这M个数的集合,然后每次随机从集合中抽一个数,抽N次即可。
等概率显然不是什么问题,当然前提是假设随机函数是等概率的,否则任何方法都免谈了。
对于其中的每一个数,它在每一次不被抽走的概率是:(M-1)/M、(M-2)/(M-1)、...、(M-N)/(M-N-1),到最后还没被抽走的概率就是(M-N)/M,也就是说它会被抽走的概率是N/M。

看到一个网友的解决思路,感觉很有意思:

在M个数中,随机取出其中的N个,那么每个数被选中的概率都是N/M。

对于其中的第一个数字,它被选中的概率是N/M,所以随机生成一个来自(0,1)之间的均匀分布的实数u。
如果u<N/M,则这个数被选中。于是问题简化为:对于剩下的M-1个数,等概率选择其中的N-1个,每个数被选中的概率都是(N-1)/(M-1);
否则,这个数字不被选中。问题简化为:对于剩下的M-1个数,等概率选择其中的N个,每个数被选中的概率都是N/(M-1);

简单分析一下概率:对于这第一个数字,它被选中的概率就是N/M。
对于剩下的M-1个数,任何一个数被选中的概率是: N/M * (N-1)/(M-1) + (1-N/M) * N/(M-1) = N/M. 因此满足题意。

这样的思路让人很受启发……


七伤
+关注
目录
打赏
0
0
0
0
52
分享
相关文章
交换两个数的值的方法(三种)
交换两个数的值的方法(三种)
81 1
|
9月前
1004.最大连续1的个数
1004.最大连续1的个数
41 0
不使用第三变量。如何对2个数进行交换
不使用第三变量。如何对2个数进行交换
101 0
判断一个数是否是对称数(数组/非数组解法)
判断一个数是否是对称数(数组/非数组解法)
【前端算法】最大连续1的个数,一次遍历
给定一个二进制数组, 计算其中最大连续1的个数。
133 0
【前端算法】最大连续1的个数,一次遍历
判断正负数个数
判断正负数个数
116 0
随机生成十个不重复的数组元素
随机生成十个不重复的数组元素
155 0