leetcode
leetcode 751 ~ 800
用 Rand7() 实现 Rand10()

用 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()的结果?
选择将(rand7() - 1)与7相乘是为了扩展rand7()生成的范围,同时保持均匀分布。由于(rand7() - 1)生成的是0到6之间的均匀随机整数,乘以7正好可以产生0, 7, 14, ..., 42这些7的倍数。这样再加上一个1到7的随机数,就可以覆盖1到49之间的所有整数,而且每个数出现的概率是相同的,从而保持了随机性和均匀性。
🦆
在实现中,将结果限制在1到40之间而不是直接使用1到49的结果进行模运算有什么特别的原因吗?
将结果限制在1到40之间而不直接使用1到49的结果进行模运算,是为了确保每个数字在最终输出1到10的映射中出现的概率完全相同,从而保持均匀分布。如果直接从1到49映射到1到10,那么1到9的数字会比10出现的概率稍高(因为49不能被10整除,导致1到9各有5个映射,而10只有4个)。限制在40以内,每个数字映射到1到10的数量都是4个,确保了均匀性。
🦆
如果rand7() - 1生成的是0到6,那么(rand7() - 1) * 7 + rand7()生成的数列是否真的能够均匀覆盖1到49的所有数字?
是的,(rand7() - 1) * 7 + rand7()确实可以均匀覆盖1到49的所有数字。这是因为(rand7() - 1) * 7生成的是0到42之间的7的倍数,每次增加7。然后再通过加上一个1到7的随机数,刚好可以填补这些间隔,从而生成1到49的每一个数字。每个数字生成的概率都是1/49,保持了均匀分布。

相关问题