LeetCode 470 用 Rand7() 实现 Rand10()

摘要

LeetCode 470 这道题乍一看像是“随机数题”，但真正考的并不是 API 调用，而是**对概率、均匀分布以及拒绝采样（Rejection Sampling）**的理解。
题目限制只能用rand7()，却要生成rand10()，这类问题在工程里并不少见，比如基于受限随机源做更高维度的随机模拟、灰度实验、AB 测试分流等。

这篇文章会从直觉误区开始，一步步推到正确解法，并用 Swift 写出一个可以直接跑的 Demo，顺便聊聊它在真实系统里的意义。

描述

题目给了一个现成的方法：

rand7() -> 返回 [1, 7] 之间的均匀随机整数

我们的目标是实现：

rand10() -> 返回 [1, 10] 之间的均匀随机整数

限制条件很严格：

• 只能调用rand7()
• 不能使用系统随机函数
• 要求结果是均匀分布

很多人第一反应是：

“那我rand7() % 10 + 1不就行了？”

这个想法非常自然，但也是这道题的第一个坑。
因为7 不能整除 10，直接取模一定会导致某些数字出现的概率更高。

所以问题的本质其实是：

如何把一个有限、离散、范围不整除的随机源，映射成另一个均匀随机源？

题解答案

核心思路只有一句话：

用rand7()组合出一个更大的均匀空间，再从中“筛选”出[1,10]。

具体做法是：

1. 用两次rand7()生成一个[1,49]的均匀随机数
2. 只保留[1,40]这一段
3. 对 10 取模，映射到[1,10]

为什么是 40？
因为40是小于等于 49 的最大、能被 10 整除的数。

题解代码分析

下面是一个完整、可运行的 Swift Demo，包含rand7()的模拟实现，方便本地测试。

classSolution{// 模拟题目给定的 rand7()funcrand7()->Int{returnInt.random(in:1...7)}// 目标函数funcrand10()->Int{whiletrue{// 将 rand7() 扩展成 [1, 49]letnum=(rand7()-1)*7+rand7()// 只接受 [1, 40]ifnum<=40{return(num-1)%10+1}// 超过 40 的部分直接丢弃，重新来}}}

下面我们一行一行拆解这段逻辑。

第一步：为什么是(rand7() - 1) * 7 + rand7()

你可以把它想象成一个二维表：

• 第一次rand7()决定“行”
• 第二次rand7()决定“列”

这样一来：

• 一共 7 × 7 = 49 种组合
• 每一种组合出现的概率完全相等

结果自然就是一个均匀分布的[1,49]。

第二步：为什么只取[1,40]

这是这道题最关键的地方。

• 49 不能整除 10
• 40 可以整除 10

如果我们只使用[1,40]，那么：

• 每个数字 1～10 都对应4 个等概率来源
• 映射后仍然是均匀分布

剩下的[41,49]呢？

答案是：
不要了，直接重来。

这就是经典的拒绝采样（Rejection Sampling）。

第三步：为什么不会死循环

很多人担心：

“一直 reject，会不会一直跑不出来？”

实际上不会。

• 接受概率是40 / 49
• 平均不到 1.25 次循环就能成功一次

在进阶问题里，这正是题目希望你分析的“期望调用次数”。

示例测试及结果

我们可以简单写个测试，看看分布是不是均匀的。

letsolution=Solution()varcounter=Array(repeating:0,count:10)lettimes=100_000for_in0..<times{letvalue=solution.rand10()counter[value-1]+=1}foriin0..<10{print("Number\(i+1):\(counter[i])")}

你会看到类似这样的输出（每次略有波动）：

Number 1: 10021 Number 2: 9958 Number 3: 10044 Number 4: 10003 Number 5: 10012 Number 6: 9987 Number 7: 10031 Number 8: 9996 Number 9: 10019 Number 10: 9929

从结果上看，每个数字的出现次数都非常接近，说明分布是均匀的。

时间复杂度

单次rand10()：

• 平均调用rand7()的次数是常数级
• 接受概率是40 / 49

所以：

• 时间复杂度是 O(1)（期望意义下）

这也是为什么这种“看起来有循环”的写法，在随机问题中是完全可以接受的。

空间复杂度

• 没有使用额外的数据结构
• 只用了几个临时变量

所以：

• 空间复杂度是 O(1)

总结

LeetCode 470 表面上是一个随机数题，实际上考的是三件事：

1. 你是否真正理解“均匀分布”
2. 你能不能跳出“取模”的直觉陷阱
3. 你是否知道如何通过拒绝采样构造新概率空间

在真实业务里，这类思路经常用在：

• 灰度发布中的流量均匀分桶
• 基于有限随机源的模拟系统
• 游戏、推荐系统里的概率控制

如果你能把这道题讲清楚，说明你对“概率 + 工程实现”这件事，已经不是停留在表面了。