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。

参考链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7/solution/gong-shui-san-xie-k-jin-zhi-zhu-wei-shen-zmd4/

编码

普通版：

/**
 * 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;
            }
        }
    }
}

请添加图片描述