Question

470. 用 Rand7() 实现 Rand10()

English Version

题目描述

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

每个测试用例将有一个内部参数 n，即你实现的函数 rand10() 在测试时将被调用的次数。请注意，这不是传递给 rand10() 的参数。

 

示例 1:

输入: 1
输出: [2]

示例 2:

输入: 2
输出: [2,8]

示例 3:

输入: 3
输出: [3,8,10]

 

提示:

• 1 <= n <= 105

 

进阶:

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

解法

方法一：拒绝采样

我们可以使用拒绝采样的方法实现等概率生成任意区间的随机数。拒绝采样的思路是如果生成的随机数落在我们希望的区间内，那么就返回该随机数，否则会不断生成直到生成一个落在区间内的随机数为止。

对于本题，我们可以通过调用 $rand7()$ 两次来实现生成 $[1,10]$ 以内的随机数，具体如下：

我们生成一个大于等于 $1$ 且小于等于 $40$ 的整数 $x$，其中等概率生成的方式为 $x = (rand7() - 1) \times 7 + rand7()$，然后，我们返回 $x \bmod 10 + 1$ 即可。

期望时间复杂度为 $O(1)$，但是最坏情况下会达到无穷大的时间复杂度。空间复杂度为 $O(1)$。

# The rand7() API is already defined for you.
# def rand7():
# @return a random integer in the range 1 to 7


class Solution:
  def rand10(self):
    """
    :rtype: int
    """
    while 1:
      i = rand7() - 1
      j = rand7()
      x = i * 7 + j
      if x <= 40:
        return x % 10 + 1

/**
 * The rand7() API is already defined in the parent class SolBase.
 * public int rand7();
 * @return a random integer in the range 1 to 7
 */
class Solution extends SolBase {
  public int rand10() {
    while (true) {
      int i = rand7() - 1;
      int j = rand7();
      int x = i * 7 + j;
      if (x <= 40) {
        return x % 10 + 1;
      }
    }
  }
}

// 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 (1) {
      int i = rand7() - 1;
      int j = rand7();
      int x = i * 7 + j;
      if (x <= 40) {
        return x % 10 + 1;
      }
    }
  }
};

func rand10() int {
  for {
    i := rand7() - 1
    j := rand7()
    x := i*7 + j
    if x <= 40 {
      return x%10 + 1
    }
  }
}

/**
 * The rand7() API is already defined for you.
 * function rand7(): number {}
 * @return a random integer in the range 1 to 7
 */

function rand10(): number {
  while (true) {
    const i = rand7() - 1;
    const j = rand7();
    const x = i * 7 + j;
    if (x <= 40) {
      return (x % 10) + 1;
    }
  }
}

/**
 * The rand7() API is already defined for you.
 * @return a random integer in the range 1 to 7
 * fn rand7() -> i32;
 */

impl Solution {
  pub fn rand10() -> i32 {
    loop {
      let i = rand7() - 1;
      let j = rand7();
      let x = i * 7 + j;
      if x <= 40 {
        return (x % 10) + 1;
      }
    }
  }
}