470. 用 Rand7() 实现 Rand10()

题目描述

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

输入输出

1
2
3
4
5
6
7
8
输入: 1
输出: [2]

输入: 2
输出: [2,8]

输入: 3
输出: [3,8,10]

基本思路

拒绝采样：如果生成的随机数满足要求，那么就返回该随机数，否则会不断生成，直到生成一个满足要求的随机数为止。

利用两个Rand7()相乘可以得到[1, 49]的范围数字（只用一个的话数字范围只到[1, 7]）

利用下图的规律调用两次Rand7() 但只选取前40个数用来实现Rand10()而拒绝剩下的9个数：

  • 时间复杂度：期望时间复杂度为 O(1)，但最坏情况下会达到 O(∞)（一直被拒绝）
  • 空间复杂度：O(1)

java实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
    public int rand10() {
        int row, col, index;
        do{
            col = rand7();
            row = rand7();
            index = col + (row - 1) * 7;
        }while(index > 40);
        return 1 + (index - 1) % 10;
    }
}