一、题目
二、思路
这题要用到一个神奇的知识：
已知 rand_N() 可以等概率的生成[1, N]范围的随机数
那么：
(rand_X() - 1) × Y + rand_Y() => 可以等概率的生成[1, X * Y]范围的等概率随机数
即实现了 rand_XY()
要实现rand10()，就需要先实现rand_N()，并且保证N大于10且是10的倍数。这样再通过rand_N() % 10 + 1 就可以得到[1,10]范围的等概率随机数了。
对于随机数 randN，只要 K 是 N 的约数（或者说 N 是 K 的整数倍），都可以通过 randN 一步得到 randK：randK = (randN % K) + 1，这一条比较显然=。=
而实现rand_N()，我们可以通过最先介绍的神奇知识对rand7()进行改造，如下：
(rand7()-1) × 7 + rand7() ==> rand49()
由于此处的N不是10的倍数，就需要用到【拒绝采样】，即采样结果不在要求范围内就丢弃。
优化：利用这些范围外的数字，以减少丢弃的值，提高命中率总而提高随机数生成效率。此时可以将要拒绝的随机数看成一个新的额randM，然后对这个randM用一开始讲的方法。
如何利用一个小范围随机数，得到一个确定范围的等概率随机数？
先采用随机数的 k 进制，得到一个不小于确定范围的随机数 randK，然后对超过确定范围数进行拒绝即可。 注意，如果 K 比确定范围大太多，拒绝策略效率可能就会比较低（经常生成要拒绝的随机数），此时可以把要拒绝的随机数看成一个新的 randM，然后针对这个 randM 再思考怎么用这三个方法也得到确定范围的随机数
三、代码
# 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 True : # 等概率生成[1, 49]范围的随机数我 num = (rand7() - 1) * 7 +rand7() # 拒绝采样，并返回[1, 10]范围的随机数 if(num <= 40): return num % 10 +1 # 以下为优化部分 a = num -40 # rand 9 b = rand7() num = (a - 1) * 7 + b # rand 63 if(num <= 60): return num % 10 + 1 a = num - 60 # rand3 b = rand7() num = (a - 1) * 7 + b # rand 21 if(num <= 20): return num % 10 + 1
另外可以参考leetcode鲤鱼姐的题解：
impl Solution { // 学习一下拒绝采样: // 每一步都列出算式得出的数字分布情况, 可以加深理解 pub fn rand10() -> i32 { // 首先我们清晰一下目标分布rand10(): {1, 2, 3, 4, 5, 6, 7, 8, 9, 10} // 然后我们看看手中的rand7()能产生的分布: {1, 2, 3, 4, 5, 6, 7} // 1. 我们手中能产生的分布范围是小于目标范围的, 所以我们需要尝试拓展 // 能等概率的拓展分布的操作有 '数乘' 与 '加' // 我们试试数乘: // 1 * rand7() = {1, 2, 3, 4, 5, 6, 7} // 2 * rand7() = {2, 4, 6, 8, 10, 12, 14} // 3 * rand7() = {3, 6, 9, 12, 15, 18, 21} // 4 * rand7() = {4, 8, 12, 16, 20, 24, 28} // 5 * rand7() = {5, 10, 15, 20, 25, 30, 35} // 6 * rand7() = {6, 12, 18, 24, 30, 36, 42} // 7 * rand7() = {7, 14, 21, 28, 35, 42, 49} <-- 等会儿会使用这个 // 8 * rand7() = {8, 16, 24, 32, 40, 48, 56} // ... // 这里就有感觉啦, 为了能够产生无空的分布, 我们可以用 7 * rand7() - (rand7() - 1) // rand7() - 1 = {0, 1, 2, 3, 4, 5, 6} // 7 * rand7() - (rand7() - 1) = {1, 2, 3, 4, 5, ..., 48, 49} // 这样我们就有了一个[1, 49]的随机数生成器 // 因为采用拒绝采样的思想, 首先我们进入一个无限循环, 当得到结果就退出, 如果得不到就一直循环 loop { let range_1_to_49 = 7 * rand7() - (rand7() - 1); if range_1_to_49 <= 40 { // 因为我们要1..10的等概率分布, 所以我们只需要前40个数字, 拒绝剩下的9个 // 这里的range_1_to_49 = {1, 2, 3, 4, ..., 39, 40}, // range_1_to_49 - 1 = {0, 1, 2, 3, ..., 38, 39}, // (range_1_to_49 - 1) % 10 = {0, 1, 2, 3, ..., 8, 9} // (range_1_to_49 - 1) % 10 + 1 = {1, 2, 3, ..., 9, 10} 即为rand10() return (range_1_to_49 - 1) % 10 + 1; } // 到这里说明我们的range_1_to_49 = {41, 42, 43, 44, 45, 46, 47, 48, 49} // 我们也不要浪费它们, 用它们我们可以得到一个[1, 9]的等概率分布 let range_1_to_9 = range_1_to_49 - 40; // 我们可以用之前的思想, 使用9 * rand7()得到一个空隙为9的分布, 再把这个[1, 9]的分布插进去 // 9 * rand7() = {9, 18, 27, 36, 45, 54, 63} // range_1_to_9 - 1 = {0, 1, 2, 3, 4, 5, 6, 7, 8} // 9 * rand7() - (range_1_to_9 - 1) = {1, 2, 3, 4, 5, ..., 62, 63} let range_1_to_63 = 9 * rand7() - (range_1_to_9 - 1); if range_1_to_63 <= 60 { // 类似之前的 // 因为我们要1..10的等概率分布, 所以我们只需要前60个数字, 拒绝剩下的3个 // 这里的range_1_to_63 = {1, 2, 3, 4, ..., 59, 60}, // range_1_to_63 - 1 = {0, 1, 2, 3, ..., 58, 59}, // (range_1_to_63 - 1) % 10 = {0, 1, 2, 3, ..., 8, 9} // (range_1_to_63 - 1) % 10 + 1 = {1, 2, 3, ..., 9, 10} 即为rand10() return (range_1_to_63 - 1) % 10 + 1; } // 走到这里说明range_1_to_63 = {61, 62, 63} // 我们也不要浪费它们, 用它们我们可以得到一个[1, 3]的等概率分布 let range_1_to_3 = range_1_to_63 - 60; // 我们可以用之前的思想, 使用3 * rand7()得到一个空隙为3的分布, 再把这个[1, 3]的分布插进去 // 3 * rand7() = {3, 6, 9, 12, 15, 18, 21} // range_1_to_3 - 1 = {0, 1, 2} // 3 * rand7() - (range_1_to_3 - 1) = {1, 2, 3, 4, 5, ..., 20, 21}; let range_1_to_21 = 3 * rand7() - (range_1_to_3 - 1); if range_1_to_21 <= 20 { // 类似之前的 // 因为我们要1..10的等概率分布, 所以我们只需要前20个数字, 拒绝剩下的1个 // 这里的range_1_to_21 = {1, 2, 3, 4, ..., 19, 20}, // range_1_to_21 - 1 = {0, 1, 2, 3, ..., 18 19}, // (range_1_to_21 - 1) % 10 = {0, 1, 2, 3, ..., 8, 9} // (range_1_to_21 - 1) % 10 + 1 = {1, 2, 3, ..., 9, 10} 即为rand10() return (range_1_to_21 - 1) % 10 + 1; } // 走到这里说明range_1_to_21 = {21} // 我们没法使用它了 } -1 } }
关于拒绝采样的其他解释可以参考wiki百科：
