7.5  如何等概率地从大小为n的数组中选取m个整数

7.5 如何等概率地从大小为n的数组中选取m个整数

【出自ALBB面试题】

难度系数：★★★★☆ 被考察系数：★★★☆☆

题目描述：

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

分析与解答：

从n个数中随机选出一个数的概率为1/n，然后在剩下的n-1个数中再随机找出一个数的概率也为1/n（第一次没选中这个数的概率为（n-1）/n，第二次选中这个数的概率为1/（n-1），因此，随机选出第二个数的概率为（（n-1）/n）*（1/（n-1））=1/n），依次类推，在剩下的k个数中随机选出一个元素的概率都为1/n。因此，这种方法的思路是：首先从有n个元素的数组中随机选出一个元素，然后把这个选中的数字与数组第一个元素交换，接着从数组后面的n-1个数字中随机选出1个数字与数组第二个元素交换，依次类推，直到选出m个数字为止，数组前m个数字就是随机选出来的m个数字，且它们被选中的概率相等。实现代码如下：

程序的运行结果如下：

1 8 9 7 2 4

算法性能分析：

这种方法的时间复杂度为O（m）。