一、题目描述
给定方法 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() ?
二、思路讲解
然后我们应该知道，想要从一个大范围随机数函数，获得一个小范围随机数函数，这是非常简单的。比如我们有rand10()，想要写出rand7()，那只要不断地调用rand10()就可以了，因为rand10生成1，2，3，4，5，6，7是随机的。
那么如何利用小范围的rand7构造大范围的rand10呢？很容易想到两个rand7相乘，这样生成的数在[1, 49]上，或者用2*rand7-1，力扣的官方题解也确实是这么做的：用 Rand7() 实现 Rand10()
其实这样的方式有一个问题，就是生成的每个数字出现概率并不相同，需要再进行处理，那么们可以用另一种方式：
首先我们要知道一个常识，( randX() -1 )*Y + randY() 可以等概率地生成 [1，X*Y] 范围内的随机数。证明： randX()的范围[1, X]，randx()-1的范围就是[0, X-1]。(randx() - 1) * Y的范围是[0, (X-1)*Y]，(randx() - 1) * Y + randY()的范围自然就是[1, X * Y]。
那么，我们构建 (rand7()−1)∗7+rand7() 他在[1, 49]上生成的数字是等概率的，根据我们之前的结论，由大范围随机获得小范围随机是很容易的，所以，只要不断调用这个公式生成数字，当他生成10以内的数字，就保留，生成11以上的，就丢弃，就可以构造出rand10()了，可以写出如下代码：
/** * 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() { int num = 1000; while(num>10) { num = (rand7()-1)*7 + rand7(); } return num; } }
这个程序用来完成题目是没有问题的，但是我们可以发现，生成的数字在1~49之间，然而我们利用的数字只有1~10，有一大半的数字没有利用，这样大大地增加了while循环的次数，效率偏低。所以，我们要想个办法把剩下的数字也利用起来。
我们可以利用1~40的整数，当他%10之后，也能得到等概率的0~9之间的数字，再+1就是[1,10]了。这样，我们就利用了49个数字中的大部分，只丢弃了9个数字。
/** * 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() { int num = 1000; while(num>40) { num = (rand7()-1)*7 + rand7(); } return num%10+1; } }
是不是还可以把剩下的9个数字也利用上呢？
/** * 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() { int num = 1000; while(true) { num = (rand7()-1)*7 + rand7(); if(num<=40) { return num%10+1; } //走到这里，说明num在41~49之间，再利用随机数操作一下 num = (num-40-1)*7 + rand7(); //操作结束之后，num在0~63 if(num<=60) { return num%10+1; } //走到这里，说明num在61~63 num = (num-60-1)*7 + rand7(); //操作结束之后，num在1~21 if(num<=20) { return num%10+1; } //走到这里，说明num是21，这样，就只丢弃了一个数字，大大提升了效率 } } }
