蓄水池算法
题目：
有一个机器按自然序列的方式吐出球，有一个最多能装 K 个球的袋子。设计一种选择方式使得当机器吐出第 N 号球时（N > K ），袋子球数为 K ，且保证每个球被选进袋子的概率是 K / N
思路：
- 对于 1~K 号球，直接放入袋子内
- 对于第 i 号球（i > K ），以 K/i 的概率决定放不放入袋内。放入的话则从袋子里随机选一个替换掉
具体的算法证明就不写了，可以看看左程云大佬的《程序员面试代码指南》，这里就是记录下代码。
public int rand(int max){//产生[1,max]的随机数
return (int)(Math.random()*max)+1;
}
public int[] getKNumsRand(int k,int max){
if(max<1||k<1)
return null;
int[] res = new int[Math.min(k,max)];
for(int i=0;i<k;i++){//小于k直接放入
res[i]=i+1;
}
for(int i=k+1;i<=max;i++){
if(rand(i)<=k){ // k/i 的概率放入袋子内
res[rand(k)-1]=i;
}
}
return res;
}
等概率选取问题
题目：
给定一个长度为 N 且没有重复元素的数组 arr 和一个整数 n ，实现函数等概率随机打印 arr 中的 M 个数。
思路：
- 选数组最后一个位置作为终点 end ，随机选出 [0,end] 的一个位置 t ，并将其对应的元素打印出来
- 交换 t 和 e 上的元素，e 减一
- 重复上面的步骤，知道已经选出 M 个数
public void printRandom(int[] a,int m){
if(a==null||a.length==0||m<0)
return;
m=Math.min(a.length,m);
int cnt =0;
int i=0;
while(cnt<m){
i=(int)Math.random()*(a.length-cnt);
System.out.println(a[i]);
swap(a,i,a.length-cnt-1);
cnt++;
}
}
public void swap(int[] a,int i,int j){
int tmp = a[i];
a[i]=a[j];
a[j]=tmp;
}
