本题来自Leetcode，题目传送门：力扣

难度：中等

编程语言：Go

1. 题目介绍

给定方法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 <= 10^5

2. 解题思路

核心在于构建[1-10]的结果集，每个结果出现的概率之和不一定为1，但是单个结果出现的概率须相等。

方法一

rand10需要输出[1-10]，那么构建一个二维数组，单维长度为7。

内置元素为[1-10],为保证概率均衡，每个元素在数组中的出现次数须一致。即配置4组[1-10],每个元素被选中的概率都是1/10。多余的位置补0，随机算法逢0跳过。

可以是3组，但是0会变多，导致跳过操作变多，所以0的最优个数必须小于10。

这种方法需要额外存储样本数据，扩展性不好。

方法二

扩充随机算法的取值，有方法：`randn()*n + randn()`.接下来用rand7做证明。

rand7的取值为：{1, 2, 3, 4, 5, 6, 7},则`randn()*n`的取值为：{7, 14, 21, 28, 36, 42, 49}。

那么`randn()*n + randn()`中：8出现的概率为1/49，9出现的概率为1/49，56出现的概率为1/49。

以此归类，取值[8-56]的随机概率均衡。

当扩展的rand10时，截取取值集合[8-56]中40个数字，如[8-47]。

每个元素随机概率依旧不变，每个出现概率为1/49。

每个数字对10取余数+1，则1出现的概率就是4/40 = 1/10，其他类推，满足rand10概率均衡要求。

3. 源码展示

方法一

var arr = [][]int{
   {1, 2, 3, 4, 5, 6, 7},
   {8, 9, 10, 1, 2, 3, 4},
   {5, 6, 7, 8, 9, 10, 1},
   {2, 3, 4, 5, 6, 7, 8},
   {9, 10, 1, 2, 3, 4, 5},
   {6, 7, 8, 9, 10, 0, 0},
   {0, 0, 0, 0, 0, 0, 0},
}

func rand10() int {
   result := 0
   for result == 0 {
      result = arr[rand7()-1][rand7()-1]
   }
   return result
}

方法二

func rand10() int {
    result := 1
	for result >= 48 || result < 8 {
		result = rand7()*7 + rand7()
	}
	return result % 10 + 1
}

Leetcode运算结果

方法一：

执行用时: 8 ms

内存消耗: 5.5 MB

方法二：

执行用时: 4 ms

内存消耗: 5.5 MB

生活依然要继续，每天拿出半个小时，放下焦虑，用行动来积累更好的自己，我们一起加油！