教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载导读本篇是「算法通关手册AlgoNote」对 LeetCode 0470「用 Rand7() 实现 Rand10()」的完整题解。这道题考察的是**拒绝采样Rejection Sampling**这一随机化核心技巧如何利用一个只能生成[1,7]均匀随机数的 API构造出[1,10]的均匀随机数。读完本文你将掌握拒绝采样的构造思路、均匀性的严格证明、接受率与期望调用次数的推导方法以及如何尽量少调用 rand7()的进阶优化思路。该题同时收录于仓库的面试 100 题列表与面试 200 题列表中是随机化类题目的高频考点。题目与考点标签数学、拒绝采样、概率与统计、随机化难度中等题目链接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() 构造 [1,49] 的均匀随机数调用两次rand7()得到两个独立随机数 $a$ 和 $b$$$num 7 \times (a - 1) b$$由于 $a \in [1, 7]$所以 $a - 1 \in [0, 6]$进而 $7 \times (a - 1) b \in [1, 49]$。这是一个双射映射$(a, b)$ 共有 $7 \times 7 49$ 种等概率组合每种组合唯一对应一个 $num \in [1, 49]$因此 $num$ 在 $[1, 49]$ 上是均匀分布的每个数出现的概率均为 $\frac{1}{49}$。从另一个角度看$7 \times (a-1) b$ 本质上是把两个「七进制位」组合成一个 0~48 的数再整体加 1这与十进制中十位数字 × 10 个位数字的构造完全同构只是基数从 10 换成了 7。第二步为什么只接受 [1, 40]而不是 [1, 49]因为目标是把均匀分布从 $[1, 49]$ 压缩到 $[1, 10]$而 $49 4 \times 10 9$49 不是 10 的整数倍。如果直接对 $[1, 49]$ 取num % 10余数 $1 \sim 9$ 各会出现 5 次余数 $0$即 10、20、30、40只会出现 4 次。这样 $1 \sim 9$ 与 $10$ 的概率不相等结果不均匀。如果只接受 $[1, 40]$40 恰好是 10 的整数倍$[1, 40]$ 可以无损地平均切成 4 组每组 10 个数从而保证 $[1, 10]$ 内每个数字出现次数完全相等。于是算法流程为调用两次rand7()得到 $a$、$b$计算 $num 7 \times (a-1) b$得到 $[1, 49]$ 的均匀随机数只接受$num \in [1, 40]$ 的数若 $num \in [41, 49]$拒绝并回到第 1 步重新生成对接受的数执行 $(num % 10) 1$得到 $[1, 10]$ 的均匀随机整数。均匀性证明接受范围内的数即 $num \in [1, 40]$$num 1 \sim 10$num % 10得到 $1, 2, \dots, 9, 0$$num 11 \sim 20$、$21 \sim 30$、$31 \sim 40$同理。可见 $1 \sim 10$ 每个数字作为余数恰好出现 $4$ 次余数 $0$ 对应数字 $10$。因此条件概率下每个输出结果 $1 \sim 10$ 出现的概率完全相等均匀性得到保证。接受率与期望调用次数接受 $40$ 个数字拒绝 $9$ 个数字$41 \sim 49$单次尝试的成功率$p \frac{40}{49} \approx 0.8163$每次尝试固定调用 2 次rand7()。尝试次数服从几何分布期望尝试次数为 $\frac{1}{p} \frac{49}{40}$因此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] 范围内的数40 是 10 的整数倍可无损切分 if num 40: # 对 10 取模并加 1得到 [1, 10] 的均匀随机数 return (num % 10) 1 # 如果 num 40拒绝这个数字继续循环重新生成代码要点while True实现拒绝后重试的循环直到采样成功接受的判定条件写为num 40等价于拒绝num 40返回值(num % 10) 1余数 $0$ 对应数字 $10$其余余数 $r$ 对应数字 $r1$恰好覆盖 $[1, 10]$。思路 1复杂度分析时间复杂度$O(1)$ 期望时间复杂度。期望调用rand7()的次数为 $\frac{2 \times 49}{40} 2.45$ 次。虽然理论上可能连续拒绝但拒绝概率以几何级数衰减期望为常数。空间复杂度$O(1)$。只使用了几个额外的变量。进阶如何进一步减少 rand7() 的调用次数原题进阶提问能否尽量少调用 rand7()对应的经典优化是复用被拒绝的样本而不是简单丢弃。当前方案中$[41, 49]$ 的 9 个数被直接拒绝。但这 9 个数同样是等概率的可以把它们映射为 $[0, 8]$ 的均匀随机数saved保存下来留作下一轮采样的种子。优化后的流程第一轮照常调用两次rand7()得到 $num \in [1, 49]$若 $num \le 40$直接返回 $(num % 10) 1$否则记录saved num - 41均匀落在 $[0, 8]$后续每一轮只需再调用一次rand7()得到 $b$计算 $9 \times (b - 1) saved 1 \in [1, 63]$若 $\le 60$60 是 10 的整数倍返回 $(num % 10) 1$否则更新saved num - 61均匀落在 $[0, 2]$继续下一轮。每一轮成功率提升到 $\frac{60}{63} \frac{20}{21} \approx 0.952$期望调用次数约为$$E 2 \frac{9}{49} \times \frac{21}{20} \approx 2.19$$相比基础版的 2.45 次有所下降且代码仍是 $O(1)$ 期望时间、$O(1)$ 空间。这条优化路径是通用拒绝采样技巧的自然延伸面试中能主动提出复用被拒绝样本通常会是加分项。本题的标准解以基础版为主优化版可根据需要自行实现验证。仓库延伸拒绝采样系列题目拒绝采样并不是一道孤立的技巧。在 AlgoNote 仓库中同一标签下还有一道姊妹题0478. 在圆内随机生成点在圆的外接正方形内均匀随机生成点再判断距离是否 $\le radius$接受率恰为 $\frac{\pi}{4} \approx 0.785$。它展示了拒绝采样在连续随机场景下的应用与本题的离散随机场景形成对照。两题对比可以提炼出拒绝采样的通用模板构造一个容易采样、且包含目标区域的容器本题是 $[1,49]$ 整数区间圆形题是外接正方形使容器内样本均匀只接受落在目标区域$[1,40]$ / 圆内的样本拒绝其余并重试为保证均匀性接受区域的容量必须是目标容量的整数倍$40 4 \times 10$或使用距离判断圆形题。此外本题收录于仓库的题解总列表编号 0470并同时出现在面试 100 题列表与面试 200 题列表中足见其在随机化面试题中的地位。小结要点结论核心技巧拒绝采样构造大均匀空间 → 接受可无损切分部分 → 拒绝并重试均匀性来源$7(a-1)b$ 是 $[1,49]$ 上的双射接受域 $[1,40]$ 是 10 的整数倍接受率$p \frac{40}{49}$期望调用次数$E 2 \times \frac{49}{40} 2.45$时间复杂度$O(1)$ 期望空间复杂度$O(1)$自测建议可在本地编写一段模拟程序将rand7()替换为random.randint(1, 7)调用rand10()数万次并统计 $1 \sim 10$ 各数字的频率验证其趋近于均匀分布同时可统计平均每次rand10()实际调用rand7()的次数验证其收敛于 2.45。通过这种方式把概率论推导与工程验证结合起来才能真正吃透拒绝采样。赞分享教程文档知识库【免费下载链接】AlgoNote⛽️「算法通关手册」从零开始的「算法与数据结构」学习教程200 道「算法面试热门题目」1000 道「LeetCode 题目解析」持续更新中项目地址https://gitcode.com/gh_mirrors/le/AlgoNote点击查看免费下载相关推荐LeetCode 470 题解拒绝采样与概率论 —— 如何用 Rand7() 实现均匀的 Rand10()LeetCode 470 题解拒绝采样与概率论 —— 如何用 Rand7 实现均匀的 Rand10 导读 用 Rand7 实现 Rand10 LeetCod文档教程知识库LeetCode-Go 题解 470用 rand7() 构造均匀 rand10() 的拒绝采样原理与 Go 实现LeetCode Go 题解 470用 rand7 构造均匀 rand10 的拒绝采样原理与 Go 实现 导读 LeetCode 470 是一道经典的随机数示例工程Dopamine JAX 采样器详解UniformSamplingDistribution 均匀采样分布的实现与实战Dopamine JAX 采样器详解UniformSamplingDistribution 均匀采样分布的实现与实战 Dopamine 是面向强化学习算法快速机器学习深度学习上一篇终极jsPDF教程从零开始快速生成PDF文档的完整指南下一篇Kanboard 开源项目教程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考