leetcode：470. 用 Rand7() 实现 Rand10()

题目

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。
你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。
每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

进阶:

  • rand7()调用次数的 期望值 是多少 ?
  • 你能否尽量少调用 rand7() ?

示例：

  1. 输入: 1
  2. 输出: [2]
  1. 输入: 2
  2. 输出: [2,8]
  1. 输入: 3
  2. 输出: [3,8,10]

解答 & 代码

拒绝采样：

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

**rand7()** 调用次数的期望值：第一轮如果不被拒绝就是调用 2 次；第一轮有 9/49 的概率被拒绝，需要进行第二轮再调用 2 次；第二轮也有 9/49 的概率被拒绝… …
[中等] 470. 用 Rand7() 实现 Rand10() - 图1

  1. // The rand7() API is already defined for you.
  2. // int rand7();
  3. // @return a random integer in the range 1 to 7
  5. class Solution {
  6. public:
  7.     int rand10() {
  8.         int row = rand7() - 1;        // 行号，取值范围 [0, 6]
  9.         int col = rand7() - 1;        // 列号，取值范围 [0, 6]
  10.         int num = row * 7 + col;    // 二维矩阵拉直后，改行号列号对应的序号 num
  11.         // 如果 num >= 40，则拒绝采样，递归重新采样生成行号列号...
  12.         if(num >= 40)
  13.             return rand10();
  14.         // 如果 num < 40，则除 10 取余再 +1，得到取值范围 [1, 10]
  15.         else
  16.             return 1 + num % 10; 
  17.     }
  18. };

复杂度分析：

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

执行结果：

  1. 执行结果：通过
  3. 执行用时：4 ms, 在所有 C++ 提交中击败了 99.00% 的用户
  4. 内存消耗：7.8 MB, 在所有 C++ 提交中击败了 96.58% 的用户