0%

[Leetcode]470. Implement Rand10() Using Rand7() (C++)

题目描述

题目链接: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() 产生的所有结果组合成一个一张二维表,如下所示:

1 2 3 4 5 6 7
1
2
3
4
5
6
7

首先我们考虑以下组合:

  • (a + b):
1 2 3 4 5 6 7
1 2 3 4 5 6 7 8
2 3 4 5 6 7 8 9
3 4 5 6 7 8 9 10
4 5 6 7 8 9 10 11
5 6 7 8 9 10 11 12
6 7 8 9 10 11 12 13
7 8 9 10 11 12 13 14

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

1 2 3 4 5 6 7
1 0 1 2 4 5 6 7
2 8 9 10 11 12 13 14
3 15 16 17 18 19 20 21
4 22 23 24 25 26 27 28
5 29 30 31 32 33 34 35
6 36 37 38 39 40 41 42
7 43 44 45 46 47 48 49

有了这样的表格之后,假设获得表格的组合为 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)。将二维图表建立成一个一维索引的方法在不少题目都会用到,可以熟悉一下。代码如下所示:

1
2
3
4
5
6
7
8
9
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)