题目描述

题目链接：470. Implement Rand10() Using Rand7()

Given a function rand7 which generates a uniform random integer in the range 1 to 7, write a function rand10 which generates a uniform random integer in the range 1 to 10.

Do NOT use system’s Math.random().

例子

例子 1

Input: 1 Output: [7]

例子 2

Input: 2 Output: [8,4]

例子 3

Input: 3 Output: [8,1,10]

Note

1. rand7 is predefined.
2. Each testcase has one argument: n, the number of times that rand10 is called.

Follow up:

1. What is the expected value for the number of calls to rand7() function?
2. Could you minimize the number of calls to rand7()?

解题思路

这道题给了我们一个 rand7() 可以等概率的产生 1 到 7 之间的整数，要求我们实现一个 rand10() 等概率产生 1 到 10 的整数。这里我主要参考了这篇博客的方法（花花酱 LeetCode 470. Implement Rand10() Using Rand7()）：由于 rand7() 只能产生 7 个数，为了产生 1 到 10 我们势必要通过使用两次 rand7() 并将两者结合，最后通过一定方式等概率的生成 1 到 10。这里我们将两个 rand7() 产生的所有结果组合成一个一张二维表，如下所示：

首先我们考虑以下组合：

• (a + b):

可以发现，这种组合方式非常不规则，很难等概率从中间取出 1 到 10。为了使得结果更方便取数，与其先考虑什么组合方式，我们可以先建立一个好用的表格，再从表格中倒推我们需要用什么组合。这里我们可以以两个值作为索引，建立以下表格：

有了这样的表格之后，假设获得表格的组合为 f(a, b) 那么我们可以发现：当 f(a, b) < 40 时，我们只要令 f(a, b) 对 10 取余并加 1，得到 1 到 10 的概率是相等的。当 f(a, b) >= 40 时我们只需要重新选择两个值就可以了。而获得这样效果的组合通过观察也不难得知是：f(a, b) = 7 * (a - 1) + (b - 1)。将二维图表建立成一个一维索引的方法在不少题目都会用到，可以熟悉一下。代码如下所示：

class Solution {
public:
    int rand10() {
        int index = INT_MAX;
        while (index >= 40)
          index = 7 * (rand7() - 1) + (rand7() - 1);
        return index % 10 + 1;
    }
};

• 时间复杂度：O(1)
• 空间复杂度：O(1)