470.md

470. Implement Rand10() Using Rand7()

Description

link

---

Solution

N < M

• 如果简单重复RandN到M的某个倍数导致的问题是可能会生成重复的数字
• 如本题必须使用(rand7 - 1)*7保证生成出来的第一部分必然每段包含7个数字
• 这样第二部分rand7加上的时候不会有任何重复的数字，可以保证1 - 49每个数字产生的概率相同都是1/49
• 在这个基础上进行拒绝采样大于40的数字舍弃
• 得到小于等于40的数字进行取余数即是答案，需要+1

---

Code

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