随机问题是面试中常见的算法问题，这里做一个总结

用随机函数rand5来构造随机函数rand7

假如有一个函数rand5能等概率生成1-5 之间的整数，如何利用rand5来实现rand7？rand7函数的要求是能够等概率生成1 - 7之间的整数。

如果反过来，使用rand7构造rand5，那就比较简单了，直接rand7()%5+1，虽然这个解法不是很好(TODO 后面会修正)，但已经可以认为是正确了

但这给我们一个思路：先构造较大的随机函数！

这还不简单，直接两个rand5相加不就得到值域是[1-10]的随机函数了么？但这样的随机函数每个数字不是等概率出现的(TODO 证明)，其实，直接对两个随机函数相加，相乘都不能得到完全随机的函数，需要换个思路

先简化一下这个题目：如何等概率生成[0-3]?

[0-3]表示成二进制是[00,01,10,11]，发现，二进制的第一位和第二位满足0-1均匀分布,我们可以分别对每一位进行随机：rand1()<<1+rand1()

有了这个思路，我们可以先使用rand5构造一个随机函数(rand5()-1)*5+rand5()-1，均匀生成两位的5进制数，其等概率生成[0-24]之间的数字

在取一下模就能得到rand7，具体代码如下：

int rand7(){
    while(true){
        int res = 5*(rand5()-1)+rand5()-1;
        if(res<21)
            return res%7+1;
    }
}

一个数组，每个数字抽到的概率相等

等概率随机排列数组（洗牌算法）

假设有一个数组，包含n个元素。现在要重新排列这些元素，要求每个元素被放到任何一个位置的概率都相等（即1/n），并且直接在数组上重排（in place），不要生成新的数组。用 O(n) 时间、O(1) 辅助空间。

java.util.Collections中提供了随机重排数组的方法shuffle(List<?> list) 详见这里

单次遍历，随机选取问题

在不知道文件总行数的情况下，如何从文件中随机的抽取一行

随机抽取一行，要求每一行抽到的概率是相同的，如果知道总行数，直接哈希一个行号即可，但不知道行数下，我们遍历文件一次，如何随机抽取其中一行？

其实，可以归约到成子问题求解，即读到第k行，以1/k的概率选择其作为当前抽取对象…

带权随机选取（Weighted Random Sample）问题

一组数量未知的数据，每个元素有非负权重。要求只遍历一次，随机选取其中的一个元素，任何一个元素被选到的概率与其权重成正比。

这个的思路和上面‘单次遍历，随机选取问题’很相似，只是计算概率时加一个权重而已，时间复杂度O(N)，空间复杂度O(1)

有没有时间复杂度O(1)的算法呢，比如以空间换时间，有个思路不知对否：

设所有元素的权重之和为S,开辟一个长度为S的数组A，每个元素从A中申请其权重长度的空间，这样随机一个S范围内的数字，找到对应的空间，看看这个空间属于那个元素，就返回哪个元素