#470
中等
低频
数学用 Rand7() 实现 Rand10()
这是一道围绕算法展开的高频练习。建议先掌握「数学」这套写法,再结合下方步骤讲解理解状态维护、边界处理和复杂度取舍。
算法
题目分析
这道题表面上是在处理「用 Rand7() 实现 Rand10()」,但先要想清楚题目到底让你返回什么,以及过程中哪些约束必须一直满足。从题型上看,它主要在考 算法 这些能力。这题更重要的是把过程抽象成可证明正确的数学构造,而不是只靠模拟去碰运气。只有先把题目要求翻译成人话,后面的推荐代码才是在实现思路,而不是直接给答案。
接下来怎么看推荐代码: 带着这个理解再看推荐代码时,重点观察这条主线:把两次
rand7() 组合成均匀的 1 到 49,再用拒绝采样只保留 1 到 40 映射成 1 到 10。推荐代码
推荐解法:数学
时间复杂度: 期望 O(1)
空间复杂度: O(1)
核心思路: 把两次
rand7() 组合成均匀的 1 到 49,再用拒绝采样只保留 1 到 40 映射成 1 到 10。// Java 实现 rand10() 使用 rand7()
// 算法思路:数学方法 - 拒绝采样
class Solution extends SolBase {
/**
* 使用 rand7() 实现 rand10()
* 算法步骤:
* 1. 生成两个 rand7() 随机数 row 和 col
* 2. 计算 idx = col + (row - 1) * 7,范围是 1-49
* 3. 如果 idx > 40,重新生成(拒绝采样)
* 4. 返回 1 + (idx - 1) % 10,范围是 1-10
*/
public int rand10() {
int row, col, idx;
do {
row = rand7();
col = rand7();
idx = col + (row - 1) * 7;
} while (idx > 40);
return 1 + (idx - 1) % 10;
}
}
// 说明:SolBase 是一个基类,提供了 rand7() 方法
// 该方法返回 1-7 之间的随机整数结构化讲解
面试时怎么讲
开场思路
这题我会用拒绝采样,先造大空间,再裁掉不能均匀映射的尾部。
核心过程
- 两次
rand7()先组成 1 到 49 的等概率随机数。 - 只保留 1 到 40,因为它能均匀分成 10 组。
- 把保留结果映射到 1 到 10。
- 若落在 41 到 49,就重新采样。
复杂度总结
期望时间复杂度 O(1),空间复杂度 O(1)。
面试补一句:这题最关键的解释是“为什么要拒绝 41 到 49”。
核心思路
这题核心是先构造一个更大的均匀样本空间,再裁掉不能整除 10 的尾部区间。拒绝采样的关键是“只保留均匀可映射的部分”。
步骤讲解
1
两次 rand7 组合出 1 到 49
把第一次结果看成行、第二次结果看成列,构造 49 个等概率状态。
为什么这样做:49 是 7×7,所有组合天然等概率。
对应代码提示:int num = (rand7() - 1) * 7 + rand7();
2
拒绝 41 到 49 的结果
只保留 1 到 40,因为这 40 个值可以均匀分成 10 组。
为什么这样做:尾部 9 个值无法等分到 10 个结果,会破坏均匀性。
对应代码提示:if (num <= 40) ...
3
把 1 到 40 映射到 1 到 10
对保留值做取模映射,就得到均匀的 1 到 10。
为什么这样做:40 可以整除 10,每个结果恰好对应 4 个原状态。
对应代码提示:return (num - 1) % 10 + 1;
易错点
直接对 49 取模 10
49 不能被 10 整除,结果分布会偏斜。
正确理解:必须先拒绝掉尾部无法均匀映射的部分。
没理解两次 rand7 为什么均匀
如果说不清 49 个状态等概率,后面均匀性证明就断了。
正确理解:强调 7×7 笛卡尔积的每个格子概率相同。
把拒绝采样当成浪费
这是维持严格均匀分布的必要代价。
正确理解:解释这是期望常数次重试,而不是最坏无界失控。
复杂度与适用判断
时间复杂度:期望 O(1)
空间复杂度:O(1)
比其他方案更好在哪里:比拍脑袋凑公式可靠,拒绝采样是保证均匀性的标准办法。
适用判断:当基础随机源可组合成更大均匀空间时,优先考虑拒绝采样。
额外提醒
- 均匀性的代价是接受重试,但期望次数仍然很小。
动画演示
如果你还没完全看懂,可以展开动画演示。
数学动画演示
想看这段解法是怎么一步步运行的,可以展开动画继续观察。
数学动画演示
想看这段解法是怎么一步步运行的,可以展开动画继续观察。
准备就绪 - 点击开始按钮查看动画
动画演示仅在桌面端提供,移动端请优先阅读推荐代码与结构化讲解。