随机地从大小为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个数字,且它们被选中的概率相等。实现代码如下:
程序的运行结果为:
算法性能分析:这种方法的时间复杂度为O(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个数字,且它们被选中的概率相等。实现代码如下: