用 Rand7() 实现 Rand10()
难度:
标签:
题目描述
代码结果
运行时间: 89 ms, 内存: 18.5 MB
// 思路:使用Java Stream生成 [1, 10] 范围内的均匀随机整数。我们利用 rand7() 生成 [1, 49] 的随机数,并使用 Stream 过滤掉大于 40 的数。
// Java Stream实现
import java.util.stream.IntStream;
public class Solution {
public int rand10() {
return IntStream.generate(() -> (rand7() - 1) * 7 + rand7())
.filter(num -> num <= 40)
.findFirst()
.getAsInt() % 10 + 1;
}
// 假设这是给定的rand7()方法
private int rand7() {
return (int) (Math.random() * 7) + 1;
}
}
解释
方法:
要使用rand7()实现rand10(),关键是如何扩展rand7()生成的范围以覆盖1到10并保持均匀分布。首先,(rand7() - 1)将生成0到6的均匀分布。然后,(rand7() - 1) * 7将生成0, 7, 14, ..., 42的等差序列,这些是7的倍数。再加上另一次rand7()调用,结果为(rand7() - 1) * 7 + rand7(),这可以生成1到49之间的均匀分布的数字。接下来,为了得到1到10的均匀分布,我们只取1到40之间的结果,因为40是最接近49的可以被10整除的数。这样1到40的每个数字都有相同的概率出现。最后,使用(index - 1) % 10 + 1将1到40的数字映射到1到10的范围。
时间复杂度:
O(1)
空间复杂度:
O(1)
代码细节讲解
🦆
为什么选择将(rand7() - 1)与7相乘,而不是选择其他数字乘以rand7()的结果?
▷🦆
在实现中,将结果限制在1到40之间而不是直接使用1到49的结果进行模运算有什么特别的原因吗?
▷🦆
如果rand7() - 1生成的是0到6,那么(rand7() - 1) * 7 + rand7()生成的数列是否真的能够均匀覆盖1到49的所有数字?
▷