leetcode_470. 用 Rand7() 实现 Rand10()

2 minutes read
LeetCode
面试 • 算法 • 数据结构

用 Rand7() 实现 Rand10()

题目

已有方法 rand7 可生成 1 到 7 范围内的均匀随机整数，试写一个方法 rand10 生成 1 到 10 范围内的均匀随机整数。

不要使用系统的 Math.random() 方法。

示例 1:
输入: 1
输出: [7]

示例 2:
输入: 2
输出: [8,4]

示例 3:
输入: 3
输出: [8,1,10]

提示:

rand7 已定义。 传入参数: n 表示 rand10 的调用次数。

进阶:

  1. rand7()调用次数的 期望值 是多少 ?
  2. 你能否尽量少调用 rand7() ?

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/implement-rand10-using-rand7 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路

舍弃法

  • 一次 rand7() 生成的是 1~7 的 等概率数字

  • 两次 rand7() 生成的是 1~49 的 等概率数字

  • 舍弃 41 ~ 49 的情况，继续生成，直到 1 ~ 40， 对10取余数 +1 即可得到等概率的 1~10

优化

生成 41 ~ 49 的时候也可以接受，即在1~9基础上再 rand7()，生成1~63

  • 1 ~ 60 对10取余数 +1 即可得到等概率的 1~10
  • 61 ~ 63 (1~3) 再 rand7() ，范围是 1 ~ 21，这时候直接丢弃1吧

解答

func rand10() int {
    index := (rand7()-1)*7 + rand7()
    for index > 40 {
       index := (rand7()-1)*7 + rand7() 
    }
    return index%10 + 1
}
// 执行用时 :16 ms, 在所有 Go 提交中击败了36.23%的用户
// 内存消耗 :4.8 MB, 在所有 Go 提交中击败了100.100%的用户

// 优化
func rand10() int {
    for {
        // 两个rand7() 生成 1~49
        index := rand7() + (rand7()-1)*7
        if index <= 40 {
            return index%10 + 1
        }

        // 利用多出来的 1~9，生成 1~63
        index = rand7() + (index-40-1)*7
        if index <= 60 {
            return index%10 + 1
        }

        // 利用多出来的 1~3，生成 1~21
        index = rand7() + (index-60-1)*7
        if index < 20 {
            return index%10 + 1
        }
    }
}
// 执行用时 :12 ms, 在所有 Go 提交中击败了91.30%的用户
// 内存消耗 :4.8 MB, 在所有 Go 提交中击败了100.100%的用户

分享：