LeetCode470 用 Rand7() 实现 Rand10()

发表于 | 分类于 |
字数统计: 383 | 阅读时长 ≈ 1

链接: https://leetcode.cn/problems/implement-rand10-using-rand7/

题意

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

解法

是一道很神奇的题目，用一个随机数生成器实现另一个随机数生成器。
就这道题而言，可以先获得一个随机数2生成器，再获得一个随机数5生成器
这个的获得比较容易，只要随机出来的结果在范围内即可
然后 1 / 2 * 1 / 5 = 1 / 10

一个通用的解法是，用小数生成大数的生成器可以用下式来进行生成

其中，rand_N() 可以等概率的生成[1, N]范围的随机数
通过上式，就得到了等概率的生成[1, X * Y]范围的随机数，即实现了 rand_XY()

因此本题中，用rand7通过上式得到rand49，再通过拒绝采样，去掉超过40的数
再取模就可以得到rand10

代码

解法一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7
class Solution {
public:
    int rand10() {
        int res = 0;
        int a = 10, b = 10;
        while(a > 2) {
            a = rand7();
        }
        while (b > 5) {
            b = rand7();
        }
        return a & 1 ? b : b + 5;
    }
};

解法二

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
// The rand7() API is already defined for you.
// int rand7();
// @return a random integer in the range 1 to 7

class Solution {
public:
    int rand10() {
        while (true) {
            int temp = (rand7() - 1) * 7 + rand7();
            if (temp <= 40) {
                return (temp - 1) % 10 + 1;
            }
        }
    }
};