---

0470. 用 Rand7() 实现 Rand10()

• 标签：数学、拒绝采样、概率与统计、随机化
• 难度：中等

题目链接

• 0470. 用 Rand7() 实现 Rand10() - 力扣

题目大意

描述：

给定方法 rand7 可生成 $[1,7]$ 范围内的均匀随机整数。

要求：

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

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

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

说明：

• $1 \le n \le 10^{5}$。

• 进阶:

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

示例：

• 示例 1：

输入: 1
输出: [2]

• 示例 2：

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

解题思路

思路 1：拒绝采样

我们可以通过拒绝采样（Rejection Sampling）的方法，用 rand7() 生成 rand10()。

具体思路：

1. 调用两次 rand7()，生成两个随机数 $a$ 和 $b$。
2. 通过 $7 \times (a-1) + b$ 生成 $[1, 49]$ 范围内的均匀随机整数（因为 $a \in [1, 7]$，$b \in [1, 7]$，所以 $a-1 \in [0, 6]$，$7 \times (a-1) + b \in [1, 49]$）。
3. 只接受 $[1, 40]$ 范围内的数，拒绝 $[41, 49]$ 的数，如果被拒绝则重新生成。这样我们可以得到 $[1, 40]$ 范围内均匀分布的随机数。
4. 将接受的数字对 $10$ 取模并加 $1$，即 $(num \% 10) + 1$，得到 $[1, 10]$ 范围内的均匀随机整数。

为什么只接受 $[1, 40]$ 而不接受 $[1, 49]$？

• 因为我们需要生成 $[1, 10]$ 的均匀随机数。
• 如果接受 $[1, 49]$，那么 $1-9$ 会出现 $5$ 次，$10$ 会出现 $4$ 次，这样就不均匀了。
• 如果只接受 $[1, 40]$，那么每个数字 $[1, 10]$ 都会出现恰好 $4$ 次，保证了均匀性。

接受率的计算：

• 接受 $40$ 个数字，拒绝 $9$ 个数字。
• 接受率为 $p = \frac{40}{49} = \frac{40}{49}$。
• 期望调用 rand7() 的次数为 $E = 2 \times \frac{49}{40} = 2.45$。

思路 1：代码

# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7

class Solution:
    def rand10(self):
        """
        :rtype: int
        """
        while True:
            # 第一次调用 rand7() 生成 [1, 7] 的随机数 a
            a = rand7()
            # 第二次调用 rand7() 生成 [1, 7] 的随机数 b
            b = rand7()
            # 生成 [1, 49] 范围内的均匀随机数
            num = 7 * (a - 1) + b
            # 只接受 [1, 40] 范围内的数
            if num <= 40:
                # 对 10 取模并加 1，得到 [1, 10] 的均匀随机数
                return (num % 10) + 1
        # 如果 num > 40，拒绝这个数字，继续循环重新生成

思路 1：复杂度分析

• 时间复杂度：$O(1)$ 期望时间复杂度。期望调用 rand7() 的次数为 $\frac{2 \times 49}{40} = 2.45$ 次。
• 空间复杂度：$O(1)$。只使用了几个额外的变量。