蓄水池算法和等概率选取问题

蓄水池算法

题目：

有一个机器按自然序列的方式吐出球，有一个最多能装 K 个球的袋子。设计一种选择方式使得当机器吐出第 N 号球时（N > K ），袋子球数为 K ，且保证每个球被选进袋子的概率是 K / N

思路：

1. 对于 1~K 号球，直接放入袋子内
2. 对于第 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 个数。

思路：

1. 选数组最后一个位置作为终点 end ，随机选出 [0,end] 的一个位置 t ，并将其对应的元素打印出来
2. 交换 t 和 e 上的元素，e 减一
3. 重复上面的步骤，知道已经选出 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;
}