单遍历取等概率随机数问题

 问题描述：

假设我们有一堆数据（可能在一个链表里，也可能在文件里），数量未知。要求只遍历一次这些数据，随机选取其中的一个元素，任何一个元素被选到的概率相等。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说明文档。

 

 

 

单遍历取等概率随机数问题求解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