470. 用 Rand7() 实现 Rand10()
2021-09-05 LeetCode每日一题
链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/
标签：数学、拒绝采样、概率与统计、随机化
题目
已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。
示例 1:
输入: 1
输出: [7]
示例 2:
输入: 2
输出: [8,4]
示例 3:
输入: 3
输出: [8,1,10]
提示:
- rand7 已定义。
- 传入参数: n 表示 rand10 的调用次数。
进阶:
- rand7()调用次数的 期望值 是多少 ?
- 你能否尽量少调用 rand7() ?
分析
题目需要均匀随机整数，所以需要确保生成每个数的概率是相同的。
rand7()生成[1, 7]的均匀随机整数，定量整体偏移后，依然满足等概率生成。所以在rand7()生成结果的基础上进行-1操作后生成[0, 6]依然是满足条件的。
但如果对输出域进行拼接/叠加是不满足等概率生成的。比如两个rand7() + rand7()生成结果的范围是[2, 14]，但并不是每个数生成的概率都相等。生成2的概率 = 1/7 * 1/7 + 1/7 * 1/7 = 2/49，生成4的概率 = 1/7 * 1/7 + 1/7 * 1/7 + 1/7 * 1/7 + 1/7 * 1/7 = 4/49。因为1 3和2 2相加都等于4。
对生成结果进行组合满足等概率生成。比如一个rand7()生成2，一个rand7()生成6，那么组合成26是唯一的。我可以先对生成的结果进行-1操作，然后再进行组合，其实就生成了一个7进制的数。
根据「进制转换」的相关知识，如果我们存在一个 randK 的函数，对其执行 n 次，我们能够等概率产生 [0, K^n - 1] 范围内的数值。
（1）普通版：在这里我们只需要执行两次rand7()函数，就能等概率生成[0, 48]范围内的数，再把[1, 10]范围的数返回即可。
（2）进化版：上面的时间复杂度可能是O(1)，也可能是O(∞)。为了减少rand7()函数的调用，其实可以对结果等比例进行扩大，这样产生符合条件的数的概率就更大。
对于[1, 10]范围内的，我们可以扩大到[1, 40]，1对应1,11,21,31，2对应2,12,22,32， ....，10对应10,20,30,40。然后对[1,40]范围内的数，只需要对10取余+1即可。
那么禁不住想问了，每多调用一次rand7()，结果的范围值就会变大，比如调用3次，生成的结果范围在[0, 342]，那么等比例扩大到[1, 340]，会不会更快呢？我试了下，和调用两次差别不大。然后我尝试调用4次，5次，发现时间是越来越长的。
（3）rand7 的期望调用次数：在 [0, 48]中我们采纳了 [1, 40] 范围内的数值，即以调用两次为基本单位的话，有 40/49的概率被接受返回（成功）。成功的概率40/49，那么触发成功所需次数（期望次数）为其倒数 49/40 = 1.225 ，每次会调用两次 rand7，因而总的期望调用次数为 1.225 * 2 = 2.45。
编码
普通版：
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
while (true) {
int num = (rand7() - 1) * 7 + (rand7() - 1);
if (num >= 1 && num <= 10) {
return num;
}
}
}
}
请添加图片描述
进化版：
/**
* The rand7() API is already defined in the parent class SolBase.
* public int rand7();
* @return a random integer in the range 1 to 7
*/
class Solution extends SolBase {
public int rand10() {
while (true) {
int num = (rand7() - 1) * 7 + (rand7() - 1);
if (num >= 1 && num <= 40) {
return (num % 10) + 1;
}
}
}
}
请添加图片描述
