470. Implement Rand10() Using Rand7()

Loading...LeetCode

随机数 n, m 之间的映射，就是通过对若干个生成的 n 进行运算，均匀化最终结果，并拒绝掉不需要的，来获得对 m 的均匀生成，两个核心要点：

1. 运算后的 n 一定要均匀分布。 e.g. 这题的用 7 取 10，直接拿 rand7() + rand7() 然后拒绝 11-14 是不行的，没法拿到 1； rand7() + rand7() - 1 然后拒绝 11-13 也不行，因为 1- 10 没有均匀分布（结果1只有 1+1-1 一个可能，1/49，结果4 却有四种 2+3-1 or 3+2-1 or 1+4-1 or 4+1-1）。

2. 拒绝后要重抽的话，一定要整个重抽（不保留任何确定值）。

力扣

回到这题，可以取两次 rand7，计算 x + 7 * y - 7 可以获得 1-49 之间的均质随机数，如果落在 41-49 之间就重新取，1-40 就直接取余。

# 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
        """
        
        n = rand7() + (rand7() - 1) * 7
        while n > 40:
            n = rand7() + (rand7() - 1) * 7
        return 1 + n % 10