LeetCode面试题解析：用Rand7()实现Rand10()的算法与优化

1. 问题背景与需求分析这道LeetCode经典面试题要求我们仅用Rand7()这个生成1-7均匀随机数的函数构造出Rand10()函数生成1-10的均匀随机数。看似简单的需求背后实际上考察了几个关键知识点基础概率论应用均匀分布的性质拒绝采样(Rejection Sampling)方法算法效率优化最小化Rand7()调用次数位运算的巧妙运用在实际面试中类似问题经常出现在Google、Facebook等大厂的算法轮次。我曾在某次技术面试中遇到变种题目用Rand5()实现Rand7()当时因为没有系统研究过这类问题而表现不佳后来专门对此类问题进行了深入研究。2. 基础解法与概率分析2.1 直观思路与问题最直观的想法可能是def rand10(): return rand7() rand7() % 4但这种写法存在明显问题结果范围是1-10但各数字出现概率不均等例如数字1只能通过(10)得到而数字5可以通过(14)、(23)、(32)、(41)、(50)多种组合关键点必须确保1-10每个数字出现的概率严格等于1/102.2 拒绝采样基础实现标准解法是采用拒绝采样策略def rand10(): while True: num (rand7() - 1) * 7 rand7() # 1-49 if num 40: return num % 10 1原理分析(rand7()-1)*7生成0,7,14,21,28,35,42均匀分布再加rand7()得到1-49的均匀分布只取1-40的值拒绝41-49对10取模得到0-9加1即为1-10效率分析每次循环成功概率40/49 ≈ 81.63%期望调用Rand7()次数2/(40/49) 2.45次3. 优化方案与数学证明3.1 利用拒绝样本提高效率可以进一步利用被拒绝的样本41-49def rand10(): while True: a rand7() - 1 b rand7() - 1 num a * 7 b # 0-48 if num 40: return num % 10 1 # 利用剩余样本40-48 a num - 40 # 0-8 b rand7() - 1 # 0-6 num a * 7 b # 0-62 if num 60: return num % 10 1 # 继续利用剩余样本60-62 a num - 60 # 0-2 b rand7() - 1 # 0-6 num a * 7 b # 0-20 if num 20: return num % 10 1优化效果首次成功概率40/49 ≈ 81.63%二次成功概率9/49 * 60/63 ≈ 17.46%三次成功概率9/49 * 3/63 * 20/21 ≈ 0.89%期望调用次数降至约2.212次Rand7()3.2 数学期望严格证明定义随机变量X为所需Rand7()调用次数其期望E[X]计算如下E[X] 2*(40/49) 4*(9/49)(60/63) 6(9/49)(3/63)(20/21) (递归部分可忽略高阶小量) ≈ 2.212这比基础方案的2.45次有显著提升。4. 位运算优化技巧4.1 二进制位利用法观察到7和10的二进制表示7 011110 1010可以构造基于位的随机数生成def rand10(): while True: # 生成3位二进制数0-7 bits (rand7() 1) 2 | (rand7() 1) 1 | (rand7() 1) if bits 10: return bits 1特点每次尝试需要3次Rand7()调用成功概率10/1662.5%期望调用次数3/(10/16)4.8次效率较低4.2 混合位运算方案结合拒绝采样和位运算def rand10(): while True: # 首先生成0-15的均匀分布 num (rand7() 1) 3 | (rand7() 1) 2 | (rand7() 1) 1 | (rand7() 1) if 1 num 10: return num elif num 0: continue else: # 对11-15减去10得到1-5 return num - 105. 测试验证与边界情况5.1 验证均匀性的测试代码from collections import defaultdict def test_rand10(): counts defaultdict(int) test_times 100000 for _ in range(test_times): counts[rand10()] 1 for num in range(1, 11): print(f{num}: {counts[num]/test_times:.4f}) # 期望每个数字出现概率≈0.15.2 边界情况处理确保不会返回0或10的数字处理rand7()返回值范围确保是1-7整数溢出问题Python无需考虑但其他语言需要注意6. 实际面试中的变种问题6.1 常见变种题型用Rand5()实现Rand7()用RandN()实现RandM()非均匀随机数生成器的转换6.2 通用解法框架找到最小的k使得N^k M生成[0, N^k-1]范围内的均匀分布拒绝采样直到结果落在[0, M-1]范围内返回结果16.3 效率优化原则最大化接受概率尽可能复用被拒绝的样本考虑位运算等优化手段7. 工程实践中的注意事项随机数质量确保基础Rand7()是真正的均匀分布性能考量在性能敏感场景选择调用次数更少的方案可读性权衡优化方案往往牺牲可读性需根据场景选择测试覆盖必须验证输出分布的均匀性线程安全如果Rand7()有状态需要考虑同步问题我在实际项目中曾遇到过需要生成特定范围随机数的需求最终采用了类似拒绝采样的方案。经过测试发现当拒绝概率较高时如用Rand5()实现Rand7()算法的实际性能会成为瓶颈。这时可以考虑预生成随机数池的方案来优化性能。