用 Rand7() 实现 Rand10()

LC470. 用 Rand7() 实现 Rand10()

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

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

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

输入: 1
输出: [2]

思路：拒绝采样 + 减少调用次数的期望

可以调用两次 Rand7() 得到 1 ~ 49，且每个数字的概率都是 1/49，同时排除 41 ~ 49，得到个位数为 0 ~ 9 的概率都是 4/49
减少调用次数的期望：如果两次 Rand7() 得到的值小于等于 40，则直接返回，否则将剩余的值 * 7 + Rand7()

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18


class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int x = (rand7() - 1) * 7 + rand7(); // 1 ~ 49
            if (x <= 40) {
                return x % 10 + 1;
            }
            x = (x - 41) * 7 + rand7();   // 1 ~ 63
            if (x <= 60) {
                return x % 10 + 1;
            }
            x = (x - 61) * 7 + rand7();   // 1 ~ 21
            if (x <= 20) {
                return x % 10 + 1;
            }
        }
    }
}

用 Rand7() 实现 Rand10()

LC470. 用 Rand7() 实现 Rand10()

思路：拒绝采样 + 减少调用次数的期望

相关文章：