470. 用 Rand7 实现 Rand10
难度：中等 | 主题：数学、概率、拒绝采样
题目
已有 rand7() 生成 17 均匀随机整数，实现 10 均匀随机整数。rand10() 生成 1
示例
输入：n = 1
输出：[1,10] 范围内的均匀随机整数
思路
先讲个故事：抽奖转盘
你有一个 7 格的转盘（rand7），想做一个 10 格的转盘（rand10）。直接映射不行——7 和 10 不整除，概率不均匀。
你的办法：转两次 7 格转盘，组成一个 7×7=49 格的大转盘。然后只取前 40 格（40 是 10 的倍数），映射到 1~10。剩下 9 格不要，重新转。这就是拒绝采样。
引导式推导：构造均匀分布
graph TD A["rand7() × 7 + rand7()"] --> B["生成 1~49 均匀分布"] B --> C{"num ≤ 40?"} C -->|Yes| D["(num-1) % 10 + 1<br/>映射到 1~10"] C -->|No| E["拒绝, 重新采样"]
为什么 (rand7()-1)*7 + rand7() 生成 149？等概率生成 06 再乘 7 = 0,7,14,21,28,35,42，再加 17 → 149。
代码
def rand10(self):
while True:
num = (rand7() - 1) * 7 + rand7()
if num <= 40:
return (num - 1) % 10 + 1
复杂度
| 指标 | 值 | 解释 |
|---|---|---|
| 期望调用次数 | O(1) | 成功概率 40/49，期望 ≈ 1.225 次 |
| 空间 | O(1) | 几个变量 |
实战考量
频率分析
出现在：数学+概率经典题。考察拒绝采样的思想和构造能力。字节/Google 常考。
延伸思考
Q：为什么用 (rand7()-1)*7 + rand7()？
A：这是生成 1~49 均匀分布的经典构造。第一个 rand7 决定 7 个”区间”，第二个 rand7 决定区间内的偏移。
Q：为什么拒绝 41~49？
A：40 是 10 的倍数，140 可以均匀分成 10 组，每组 4 个数映射到同一个结果。4149 共 9 个数无法均匀分配，所以拒绝。
Q：期望调用次数是多少？
A：每次成功概率 40/49，期望约为 49/40 ≈ 1.225 次。
Q：如果 rand7 改成 rand5 实现 rand7？
A：同样的拒绝采样思路：用两个 rand5 构造 125，取 121（21 是 7 的倍数），拒绝 22~25。
易错点
-
(rand7() - 1) * 7不是rand7() * 7 -
num 范围是 1
49 不是 048 -
映射要用
(num - 1) % 10 + 1而不是num % 10
生活类比
拒绝采样 → 不合适的简历直接扔
HR 要招 10 个人，但收到的简历编号是 1
49。HR 只取编号 140 的简历来（因为 40 正好是 10 的倍数，可以公平分配），编号 41~49 的直接扔掉重投。虽然浪费了 9 份简历，但保证了公平性。
相关题目
| 题目 | 关系 |
|---|---|
| 136只出现一次的数字 | 数学类 |
| 191位1的个数 | 数学类 |
→ 返回题单：LeetCode学习路线图 > 十四、数学与位运算
速记卡（面试闪卡）
Q1：一句话讲清「470. 用 Rand7 实现 Rand10」到底是什么？
A：已有能生成 17 均匀随机数的 rand7()，要实现生成 110 均匀随机数的 rand10()。核心是概率里的拒绝采样（Rejection Sampling）。
Q2：题目与抽奖转盘 —— 怎么理解？
A：像你有个 7 格转盘想做 10 格转盘——直接映射不行，7 和 10 不整除，概率不均匀。办法是转两次 7 格组成 7×7=49 格大转盘，只取前 40 格映射到 1~10，剩下 9 格不要、重新转，这就是拒绝采样。
Q3：构造均匀分布 —— 怎么理解？
A：用 (rand7()-1)*7 + rand7() 生成 149 均匀分布——第一个 rand7 决定 7 个区间、第二个决定区间内偏移。只要 10；41~49 拒绝重转。num <= 40，就 (num-1) % 10 + 1 映射到 1
Q4：代码与易错 —— 怎么理解？
A：外层 while True 循环采样。易错点：(rand7()-1)*7 不是 rand7()*7；num 范围是 149 不是 048；映射要用 (num-1)%10+1 而不是 num%10。
Q5：复杂度与变体 —— 怎么理解？
A：每次成功概率 40/49，期望调用约 49/40 ≈ 1.225 次，所以期望 O(1)。反向也能做：用两个 rand5 构造 125，取 121（7 的倍数）实现 rand7。
Q6：核心速记主线有哪些？
A：题目、拒绝采样思想、49 格构造、前 40 映射、期望次数、反向变体。
口诀
A：七转十靠拒绝采样，两次七组四十九；
前四十格均匀取，余九重转莫嫌烦。