470. 用 Rand7() 实现 Rand10()

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

示例 1:

输入: 1
输出: [2]

示例 2:

输入: 2
输出: [2,8]

示例 3:

输入: 3
输出: [3,8,10]

提示:

• 1 <= n <= 105

进阶:

• rand7()调用次数的 期望值 是多少 ?
• 你能否尽量少调用 rand7() ?

数学

(rand_X() - 1) × Y + rand_Y() 可以等概率的生成[1, X * Y]范围的随机数。

class Solution extends SolBase {
    public int rand10() {
        while(true) {
            int num = (rand7() - 1) * 7 + rand7(); // 等概率生成[1,49]范围的随机数
            if(num <= 40) return num % 10 + 1; // 拒绝采样，并返回[1,10]范围的随机数
        }
    }
}

• 时间复杂度：期望时间复杂度为 O(1)，但最坏情况下会达到 O(∞)（一直被拒绝）。
• 空间复杂度：O(1)。

优化

利用范围外的数字减少丢弃的值，提高命中率从而提高随机数生成效率。运行时间也会大大减少。

期望等于次数乘以概率再求和。第一轮无条件发生，因此概率是1，每一轮都会执行两次独立的rand7()。 第一轮失败的概率是9/49，因此第二轮出现的概率是9/49……第一轮中只要有一次失败就会进入第二轮，因此第二轮的概率是9/49不是9/49的平方。

• 函数调用次数的期望：我们来分析方法一在平均情况下需要调用 $\operatorname{Rand} 7$ () 的次数。 我们称连续调用两次 $\operatorname{Rand} 7\left(\right)$ 为一轮， 在第一轮中，有 $\frac{40}{49}$ 的概率被接受，而有 $\frac{9}{49}$ 的概率被拒绝，进入第二轮随机； 第二轮有 $\left(\frac{9}{49}\right)^2$ 被拒绝， 由此推理我们可以知道第 $n$ 轮被拒绝的概率为 $\left(\frac{9}{49}\right)^n$ 。因此方法一调用 Rand7() 的期望次数为:

$$\begin{aligned} E(\# \text { calls }) & =2+2 \cdot \frac{9}{49}+2 \cdot\left(\frac{9}{49}\right)^2+\ldots \\ & =2 \sum_{n=0}^{\infty}\left(\frac{9}{49}\right)^n \\ & =2 \cdot \frac{1}{1-\frac{9}{49}} \\ & =2.45 \end{aligned}$$

我们减小随机被拒绝的概率，从而减小 RandY() 的调用次数的期望，即可减少 RandY() 的平均调用次数。

• 我们可以通过合理地使用被拒绝的采样，从而对方法—进行优化。在方法一中，我们生成 $[1,49]$ 的随机数， 若生成的随机数 $x$ 在 $[41,49]$ 中，我们则拒绝 $x$ 。然而在 $x$ 被拒绝的情况下，我们得到了一个 $[1,9]$ 的随机数， 如果再调用一次 Rand7()，那么就可以生成 $[1,63]$的随机数（即$1\cdot\frac{9}{49}$）。 我们保留 $[1,60]$ 并拒绝 $[61,63]$ ：这是 $[1,3]$ 的随机数。我们继续调用 Rand(7) ， 生成 $[1,21]$ 的随机数（即$1\cdot\frac{9}{49}\cdot\frac{3}{63}$）， 保留 $[1,20]$ 并拒绝 [1]。此时 [1] 已经没有任何用处，若出现了拒绝 1 的情况， 我们就重新开始生成 $[1,49]$ 的随机数（即第二个括号）。我们可以算它的期望如下：

• 有$9/49$的概率进行第二次rand7，有$9/49*3/63$的概率进行第三次rand7， 没有第四次了，如果第三次出现1，则从头开始。从头开始的概率是$\frac{9}{49} \cdot \frac{3}{63} \cdot \frac{1}{21}$。

• $$\begin{aligned} E(\# \text { calls }) & =\left(2+1 \cdot \frac{9}{49}+1 \cdot \frac{9}{49} \cdot \frac{3}{63}\right)+\left(\frac{9}{49} \cdot \frac{3}{63} \cdot \frac{1}{21}\cdot E(\#calls)\right) \\ & =\left(2+\frac{9}{49}+\frac{9}{49} \cdot \frac{3}{63}\right) \cdot \frac{1}{1-\frac{9}{49} \cdot \frac{3}{63} \cdot \frac{1}{21}} \\ & \approx 2.19333 \end{aligned}$$

2是因为每一轮都要调用两次rand7，用来生成a和b。第一轮发生的概率是1，所以期望是2乘以1=2.

第二轮调用发生的概率是9/49，所以期望是2乘以9/49.

注意第一次执行两次rand7，第二次和第三次都只需执行1次rand7，因为另一个数是上一轮剩下的。

class Solution extends SolBase {
    // 使用 rand7() 函数生成 1 到 10 的随机数
    public int rand10() {
        while (true) { // 不断循环，直到生成符合条件的随机数
            int a = rand7(); // 第一次调用 rand7()，生成 1 到 7 的随机数
            int b = rand7(); // 第二次调用 rand7()，生成 1 到 7 的随机数
            int num = (a - 1) * 7 + b; // 生成 1 到 49 的随机数
            if (num <= 40) return num % 10 + 1; // 如果生成的数在 1 到 40 之间，则直接返回 1 到 10 的随机数（拒绝采样）

            // 如果 num 大于 40，则重新采样
            a = num - 40; // num 在 41 到 49 之间，将其转换为 1 到 9 之间的数
            b = rand7(); // 再次调用 rand7()，生成 1 到 7 的随机数
            num = (a - 1) * 7 + b; // 生成 1 到 63 的随机数
            if (num <= 60) return num % 10 + 1; // 如果生成的数在 1 到 60 之间，则返回 1 到 10 的随机数

            // 如果 num 大于 60，则再次重新采样
            a = num - 60; // num 在 61 到 63 之间，将其转换为 1 到 3 之间的数
            b = rand7(); // 再次调用 rand7()，生成 1 到 7 的随机数
            num = (a - 1) * 7 + b; // 生成 1 到 21 的随机数
            if (num <= 20) return num % 10 + 1; // 如果生成的数在 1 到 20 之间，则返回 1 到 10 的随机数
        }
    }
}

• 时间复杂度：期望时间复杂度为 O(1)，但最坏情况下会达到 O(∞)（最后生成21的话会一直被拒绝）。
• 空间复杂度：O(1)。