[LeetCode]Implement Rand10() Using Rand7()

我们先思考如何用更大的randX()实现更小的randY()，有两种情况：

• 如果X % Y == 0，那么我们直接randX() % Y + 1即可。比如rand12()和rand4()，因为是整除的，所以取余之后不会改变原本的uniform distribution。
• 如果X % Y != 0，显然取余就是不行的了。比兔rand10()和rand7()，结果为1，2，3的概率就被提高了。所以我们一直call rand10()直到结果是在[1, 7]的范围之内，这样可以保证每个数字的概率仍然是uniformly distributed。

那么如果我们反过来，用更小的randY()实现更大的randX()的话。我们就要首先实现比X更大的randZ()，然后通过randZ()实现randX()。显然我们不能单纯的rand7() + rand7()或者rand7() * rand7()，这样不能保证结果是uniformly distributed的。考虑到每次generate的数字在[1, 7]范围内，减1就是[0, 6]。那么就是7进制，我们用这组基就可以构建均匀分布的更大的十进制的数，Z = (rand7() - 1) * 7 + rand7() - 1，这个就是在[0，48]范围内平均分布的随机数。我们用rand48()按照上面的方法构建rand10()即可。为了减小rand7()被call的次数，我们先构建rand40()，rand40()到rand10()的操作用简单的取余即可实现。因为每次有40/48的概率落在[0, 39]的范围内，generate符合要求的数的期望的次数为48 / 40。所以时间复杂度为O(1)。代码如下：

	// The rand7() API is already defined for you.
	// int rand7();
	// @return a random integer in the range 1 to 7
	class Solution {
	public:
	int rand10() {
	int num = 40;
	while (num >= 40)
	num = 7 * (rand7() - 1) + (rand7() - 1);
	return num % 10 + 1;
	}
	};

view raw Implement Rand10() Using Rand7().cpp hosted with ❤ by GitHub