题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。
不要使用系统的 Math.random() 方法。

解答 & 代码

解法一：拒绝采样

调用两次 rand7()，分别代表行号 row 和列号 col，row∈[1,7]，col∈[1,7]，就可以得到 7×7 的矩阵中的一个位置
给矩阵中每个格子一个标号 idx，则 idx 取值范围为 [1,49] ，根据 row、col 计算得到 idx
如果 idx 的值大于 40，那么拒绝该采样，重新调用步骤 1、2 进行采样，直到 idx <= 40
idx - 1 的取值范围为 [0,39]，除 10 取余，再加 1，就得到 [1, 10] 的随机数

**rand7()** 调用次数的期望值：第一轮如果不被拒绝就是调用 2 次；第一轮有 9/49 的概率被拒绝，需要进行第二轮再调用 2 次；第二轮也有 9/49 的概率被拒绝… …

时间复杂度：期望时间复杂度为 O(1)，但最坏情况下会达到 O(∞)（一直被拒绝）。
空间复杂度：O(1)。 ```cpp // 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() { // 调用两次 rand7()，分别代表行号和列号，可以得到一个 7×7 的矩阵中的一个位置 int row = rand7(); int col = rand7(); // idx 代表这个 7×7 矩阵的下标位置，范围为 [1, 49] int idx = (row - 1) 7 + col; // 如果 idx > 40.，拒绝本轮采样，进行下一轮采样，直到 idx <= 40 while(idx > 40) { row = rand7(); col = rand7(); idx = (row - 1) 7 + col; } // 得到 [1, 10] 的随机数 return (idx - 1) % 10 + 1; } };

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 93.47% 的用户内存消耗：8.1 MB, 在所有 C++ 提交中击败了 25.73% 的用户

<a name="oc4RL"></a>
## 解法二：合理使用被拒绝的随机数
```cpp
// 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 row, col, idx;
        while(true)
        {
            // 第一轮：生成 [1, 49] 的随机数 idx
            row = rand7();                    // [1, 7]
            col = rand7();                    // [1, 7]
            idx = (row - 1) * 7 + col;        // [1, 49]
            if(idx <= 40)        // 如果 idx 在 [0, 40] 内，不被拒绝 
                return (idx - 1) % 10 + 1;

            // 第二轮：利用上一轮被拒绝的随机数 [1, 9] 作为行号，生成 [1, 63] 的随机数
            row = idx - 40;                    // [1, 9]
            col = rand7();                    // [1, 7]
            idx = (row - 1) * 7 + col;        // [1, 63]
            if(idx <= 60)
                return (idx - 1) % 10 + 1;

            // 第三轮：利用上一轮被拒绝的随机数 [1, 3] 作为行号，生成 [1, 21] 的随机数
            row = idx - 60;                    // [1, 3]
            col = rand7();                    // [1, 7]
            idx = (row - 1) * 7 + col;        // [1, 21]
            if(idx <= 20)
                return (idx - 1) % 10 + 1;
            // 此时被拒绝的随机数范围 [0, 1]，没有任何用处，重新开始生成 [1, 49] 的随机数
        }
    }
};

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

执行结果：

执行结果：通过

执行用时：8 ms, 在所有 C++ 提交中击败了 93.47% 的用户
内存消耗：8 MB, 在所有 C++ 提交中击败了 41.73% 的用户

CodeTop 企业题库

[中等] 470. 用 Rand7() 实现 Rand10()

题目

解答 & 代码

解法一：拒绝采样