470. 用 Rand7() 实现 Rand10()
查看题目中等
算法
低频
解法一：数学
时间复杂度：O(1) | 空间复杂度：O(1) | 推荐使用
动画演示
准备就绪 - 点击开始按钮查看动画
代码实现
// 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 之间的随机整数时间复杂度：O(1)
空间复杂度：O(1)
使用拒绝采样算法，通过两个rand7()生成1-49的范围，拒绝大于40的部分，将1-40映射到1-10的范围。