面试|单遍历取等概率随机数问题算法|java

问题描述：
假设我们有一堆数据（可能在一个链表里，也可能在文件里），数量未知。要求只遍历一次这些数据，随机选取其中的一个元素，任何一个元素被选到的概率相等。O(n)时间，O(1)辅助空间（n是数据总数，但事先不知道）。

引例：
5个人抽5个签，只有一个签意味着“中签”，轮流抽签，从很久很久以前我们就认为这个是非常公平的例子，这个应该不用去怀疑吧。如果怀疑了，好吧，看下面的分析：
分析：
设Ai为第i个人抽签抽中事件，P(Ai)表示第i个人中签的概念，依题意得：
第一个人中签概率：P(A1)=1/5;
第二个人中签概率：P(A2)=4/5*1/4=1/5; (因为第二个人是在第一个人选了之后才去抽的，所以，还有4/5是第一个没有选中的，剩下的四个再去抽一个所以是1/4)
同理， P(A3)=4/5*3/4*1/3=1/5;
P(A4)=4/5*3/4*2/3*1/2=1/5;
P(A3)=4/5*3/4*2/3*1/2*1=1/5;
就样，五个人抽到的是等概率的，相信了吧。

总结公式:
【面试|单遍历取等概率随机数问题】
文章图片

java产生随机数的几种方式
1.使用Math.random()方法来产生一个随机数，这个产生的随机数是0-1之间的一个double，可以乘以一定的数，比如说乘以100，他就是个100以内的随机。（j2me没有）
2.在java.util这个包里面提供了一个Random的类，我们可以新建一个Random的对象来产生随机数，他可以产生随机整数、随机float、随机double，随机long，这个也是我们在j2me的程序里经常用的一个取随机数的方法。
3.在我们的System类中有一个currentTimeMillis()方法，这个方法返回一个从1970年1月1号0点0分0秒到目前的一个毫秒数，返回类型是long，我们可以拿他作为一个随机数，我们可以拿他对一些数取模，就可以把他限制在一个范围之内。

一般会用到java.util里面包中的，一个例子：

public class Test { public static void main(String[] args) { java.util.Random r=new java.util.Random(); for(int i=0; i<100; i++){ System.out.println("i="+i+""+r.nextInt(100)); } } }

结果打印了100个0到100（不包含100）的随机数。
看一下Random类：
还有nextFloat().nextLong()等方法，重点看看nextInt(int n)方法吧，看jdk说明文档。

参数： n - 要返回的随机数的范围。必须为正数。返回：下一个伪随机数，在此随机数生成器序列中 0（包括）和 n（不包括）之间均匀分布的 int 值。抛出： IllegalArgumentException - 如果 n 不是正数

单遍历取等概率随机数问题求解JAVA实现：

public class Test { public static void main(String[] args) { java.util.Random r=new java.util.Random(); int n= 0 ; int[] a = {12,34,56,78,9,91,87,4,5,62,12,3,41,8,89,541,11,54,36}; int selectNum = 0 ; for(int k : a){ n++ ; if(r.nextInt(n) == 0){ selectNum = k ; } } System.out.println("selectNum:"+selectNum); } }

参考：
http://www.gocalf.com/blog/random-selection.html
http://www.blogjava.net/cool2009/archive/2009/03/15/259882.html