记一道美团的面试题

470. 用 Rand7() 实现 Rand10() 【中等题】【概率】

曾经面美团的时候被问了一道概率题，后来在刷题的时候发现是leetcode的470题，特此拿出来和大家探讨。本文参考：https://mp.weixin.qq.com/s?__biz=MzI4Njc4MzMwMw==&mid=2247484055&idx=1&sn=eca727f40d19c14ad5ce8662ad9baf6b&chksm=ebd6e0bfdca169a98f1f36a3639f762443a63490cc77873b39121ee7b0cec56a3533580c4608&token=573689595&lang=zh_CN#rd

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法
rand7()已经定义，返回一个 1 到 7 范围内的均匀随机整数，可以直接调用

题目讲解

方法一：拒绝采样

【历史重难点题目】

历史重难点题目总结

【核心思想】

合理调用rand7()来生成rand10()
先举一个简单的例子，如何用rand7()来生成rand5()呢？用rand7()产生一个随机数，如果随机数是1,2,3,4,5就取，是6,7就重新生成。因为rand7()生成1,2,3,4,5的概率是一样的，都是 $\frac{1}{7}$ ，所以rand5()也是均分分布的。

【思路】

把rand7()想象成一个7面的骰子🎲，现在我们有两个骰子
第一次如果掷出1,2,3,4,5,6就掷下一个骰子；如果掷出7，就继续掷这个骰子，直到不是7为止
第二次如果掷出1,2,3,4,5就结束；如果掷出6,7，就继续掷这个骰子，直到不是6,7为止
如果第一次掷出1,2,3，则first记为0；如果第一次掷出4,5,6，则记first为5；记第二次掷出的为second
最后返回first+second

验证一下是否是均匀分布:
first为0的概率=第一次掷出1,2,3的概率= $\frac{3}{7}$
first为5的概率=第一次掷出4,5,6的概率= $\frac{3}{7}$
second为1,2,3,4,5的概率都相等= $\frac{1}{7}$
那么first+second为1,2,3,4,5,6,7,8,9,10的概率都相等 $=\frac{3}{7}*\frac{1}{7}=\frac{3}{49}$

【代码】

class Solution extends SolBase {
    public int rand10() {
        int first=rand7();
        int second=rand7();
        while(first==7)
            first=rand7();
        while(second>5)
            second=rand7();
        return (first/4==0?0:5)+second;    
    }
}

【备注】

拒绝采样还有好多方法，比如下面这一种，我们调用两次 Rand7()，那么可以生成 [1, 49] 之间的随机整数，我们只用到其中的 40 个，用来实现 Rand10()，而拒绝剩下的 9 个数
如下图，[1,10]都是等概率的

其他的方法这里就不一一列举了

class Solution extends SolBase {
  public int rand10() {
      int row, col, idx;
      do {
          row = rand7();
          col = rand7();
          idx = col + (row - 1) * 7;
      } while (idx > 40);
      return 1 + (idx - 1) % 10;
  }
}

方法二：拒绝采样的优化

【核心思想】

前面的方法是舍弃了一部分采样得到的值，但是我们也可以通过合理地使用被拒绝的采样，从而对之前的方法进行优化。

【思路】

用两个rand7()生成 [1, 49] 的随机数，若生成的随机数 x 在 [41, 49] 中，我们则拒绝 x。然而在 x 被拒绝的情况下，我们得到了一个 [1, 9] 的随机数
再调用一次 rand7()，那么就可以生成 [1, 63] 的随机数（9*7=63）
保留 [1, 60] 并拒绝 [61, 63]，在 x 被拒绝的情况下，得到了 [1, 3] 的随机数
继续调用 rand7()，生成 [1, 21] 的随机数（3*7=21），保留 [1, 20] 并拒绝 [1]。此时 [1] 已经没有任何用处，若出现了拒绝 1 的情况，我们就重新开始生成 [1, 49] 的随机数。

【代码】

class Solution extends SolBase {
    public int rand10() {
        while (true) {
            int index = rand7() + (rand7() - 1) * 7;
            if (index <= 40) {
                return 1 + (index - 1) % 10;
            }

            index = rand7() + (index - 40 - 1) * 7;
            if (index <= 60) {
                return 1 + (index - 1) % 10;
            }

            index = rand7() + (index - 60 - 1) * 7;
            if (index <= 20) {
                return 1 + (index - 1) % 10;
            }
        }
    }
}

【备注】