实现 Rand10()：python3 题解

1. 题目理解目标实现一个函数rand10()返回 1 到 10 之间的均匀随机整数。限制只能使用给定的rand7()函数它返回 1 到 7 之间的均匀随机整数。核心要求均匀分布。这意味着生成 1、2、...、10 的概率必须完全相等都是 1/10。什么是“均匀随机”如果rand10()是均匀的那么运行很多次后数字 1 出现的次数应该约等于数字 10 出现的次数。如果某个数字出现的概率偏高那就不是均匀随机。2. 为什么不能直接用数学公式以下方法的思路相对直接初学者容易直接想到但它们都是错误的错误思路 1取模return rand7() % 10 1原因rand7()只能生成 1-7。1%10是 17%10是 7永远生成不了 8、9、10。错误思路 2相加return (rand7() rand7()) % 10 1原因两个随机数相加结果不是均匀分布的。例如和为 2 只有 (1,1) 一种情况但和为 8 有 (1,7), (2,6)...(7,1) 七种情况。8 出现的概率远大于 2。这违反了均匀性。3. 核心解法拒绝采样 (Rejection Sampling)要生成均匀随机数最可靠的方法是构造一个更大的均匀空间然后从中“截取”我们需要的部分。思路推导扩大样本空间调用两次rand7()我们可以得到一个二维坐标 (,)其中 ,∈[1,7]。这就像掷两个 7 面的骰子。总共有 7×749 种可能的组合。由于rand7()是均匀的这 49 种组合中每一种出现的概率都是 1/49。映射到一维我们可以把这 49 种组合映射到数字 1 到 49。公式idx (a - 1) * 7 ba - 1的范围是 0 到 6。(a - 1) * 7的范围是 0, 7, 14, ..., 42。加上b(1 到 7) 后idx的范围正好是1 到 49。且 1 到 49 中每个数字出现的概率相等。拒绝采样我们需要 1 到 10 的均匀分布。49 不能被 10 整除。如果我们直接把 1-49 映射到 1-10会导致某些数字概率偏高。策略找到 49 以内最大的、能被 10 整除的数即40。如果生成的idx在1 到 40之间我们接受它并将其映射到 1-10。如果生成的idx在41 到 49之间我们拒绝它丢弃重新生成两个新的rand7()。映射结果对于接受的idx(1-40)使用公式(idx - 1) % 10 1即可得到 1-10。1 - 1, 11 - 1, 21 - 1, 31 - 1 (共 4 次)10 - 10, 20 - 10, 30 - 10, 40 - 10 (共 4 次)每个数字被选中的概率完全相等。解法一标准拒绝采样推荐这是最清晰、最标准的面试解法。# The rand7() API is already defined for you.# def rand7():# return a random integer in the range 1 to 7class Solution:def rand10(self)::rtype: intwhile True:# 1. 调用两次 rand7()生成两个独立的随机数 a 和 ba rand7()b rand7()# 2. 将二维坐标 (a, b) 映射为一维数字 idx范围是 [1, 49]# 解释(a-1)*7 产生 0, 7, 14...42# 加上 b (1-7) 后产生 1 到 49 的均匀分布idx (a - 1) * 7 b# 3. 拒绝采样# 我们只保留 1 到 40 的数字因为 40 是 10 的倍数# 41 到 49 的数字会被丢弃重新循环生成if idx 40:# 4. 将 1-40 映射到 1-10# (idx - 1) % 10 产生 0-9再加 1 变为 1-10return (idx - 1) % 10 1复杂度分析时间复杂度期望时间复杂度为 (1)。每次循环生成 1-49 的概率是 1。被接受idx 40的概率是 40/49。期望循环次数 1/(40/49)49/401.225 次。每次循环调用 2 次rand7()所以期望调用rand7()次数 2×1.2252.45 次。空间复杂度(1)只用了几个变量。4. 进阶优化减少 rand7() 调用次数题目进阶部分问能否尽量少调用rand7()在标准解法中当idx在 41-49 之间时共 9 个数我们直接丢弃了。这浪费了随机性。这 9 个数本身构成了一个均匀的rand9()。我们可以利用这部分的随机性结合新的rand7()继续生成而不是完全重来。优化思路第一轮生成 1-49。若 1-40返回结果。若 41-499 个数保留视为rand9()。第二轮利用上一轮的 9 个数再调用一次rand7()。新空间大小9×763。公式idx (prev_rand9 - 1) * 7 rand7()范围 1-63。若 1-60返回结果60 是 10 的倍数。若 61-633 个数保留视为rand3()。第三轮利用上一轮的 3 个数再调用一次rand7()。新空间大小3×721。公式idx (prev_rand3 - 1) * 7 rand7()范围 1-21。若 1-20返回结果。若 21彻底丢弃重新开始第一轮。这种优化可以将期望调用次数从2.45降低到约2.21次。解法二优化版代码class Solution:def rand10(self)::rtype: intwhile True:# --- 第一轮生成 1-49 ---a rand7()b rand7()idx (a - 1) * 7 b # 范围 [1, 49]if idx 40:return (idx - 1) % 10 1# --- 第二轮利用 41-49 (共 9 个数) ---# idx - 40 得到 1-9 的均匀随机数a idx - 40 # 范围 [1, 9]b rand7()idx (a - 1) * 7 b # 范围 [1, 63] (9 * 7)if idx 60:return (idx - 1) % 10 1# --- 第三轮利用 61-63 (共 3 个数) ---# idx - 60 得到 1-3 的均匀随机数a idx - 60 # 范围 [1, 3]b rand7()idx (a - 1) * 7 b # 范围 [1, 21] (3 * 7)if idx 20:return (idx - 1) % 10 1# 如果到了这里 (idx 21)说明运气很差所有随机性都用光了# 只能回到 while 开头完全重新开始5. 总结与对比特性标准解法 (解法一)优化解法 (解法二)核心思想拒绝采样拒绝采样 随机性复用代码可读性⭐⭐⭐⭐⭐ (非常清晰)⭐⭐⭐ (逻辑稍复杂)rand7() 期望调用次数2.45 次~2.21 次面试建议首选。逻辑清晰不易出错。进阶。如果面试官追问优化再提出此思路。建议理解公式(a - 1) * 7 b是将两个独立随机变量组合成一个更大范围均匀分布的标准技巧进制转换思想。理解拒绝为什么是 40 而不是 49因为 49 无法被 10 整除。为了保证均匀必须舍弃多余的部分。死循环问题虽然代码里有while True但因为每次循环都有大于 0 的概率成功40/49所以理论上几乎不可能无限循环期望次数是有限的