注册一亩三分地论坛,查看更多干货!
您需要 登录 才可以下载或查看附件。没有帐号?注册账号
x
为了方便,下面用P(event) 代表event发生的概率。
该题的Hashmap解法如下:
假如从0到n - 1之间,一共有B个数是黑名单,剩余M = n - B个数是白名单。对于在[0, M - 1]区间的M个数构建如下映射:
1. 如果该数在白名单上,则映射到自己
2. 如果该数在黑名单上,则映射到在[M, N - 1]区间内且未被映射的白名单上的数
然后一般有两种途径去实现pick()函数,而两种途径我都各有一个疑问。
途径1:
随机从[0, M - 1]中抽一个数,然后通过映射转换为白名单里面的数。
疑问1:
原题目是说说“从[0, 1]中随机抽取一个数并且不在黑名单上”。我的理解是从[0, 1]中随机抽取一个数,经过一系列转换,最后结果不能在黑名单上。如果一开始就只随机在[0, M - 1]上,似乎违背了题目初衷?([M, N - 1]的数不会被随机到)
途径2:
随机从[0, n - 1]中抽一个数,并且该数对M取模(即i modulo m), 然后通过映射转换为白名单里面的数。
疑问2:
假如我们有[0, 1, 2, (3), 4, 5, 6, 7, 8, (9)] 10个数,其中括号内的是黑名单的数。这时M = 8。同时我们有映射
0 -> 0
1 -> 1
2 -> 2
(3) -> 8
4 -> 4
5 -> 5
6 -> 6
7 -> 7
8 -> 8
这时,
P(最终输出结果为0)= P(随机到第0位) + P(随机到第8位) = 1/10 + 1/10 = 2/10
P(最终输出结果为7)= P(随机到第7位) = 1/10
明显各个最终输出结果的概率不尽相同,不符合题目说的“Any integer that is in the mentioned range and not in blacklist should be equally likely to be returned.”
(但是P(随机挑选数k并且返回的是白名单上数)对于各个随机到的数都是等概率的,因为,对于给定数k,一开始随机从[1, n - 1]选到它的概率为1/n。然后通过取模,数的范围必然落在[0, M - 1], 概率为1。然后映射保证最后结果是白名单上的,概率同为1。所以总概率是1/n * 1 * 1 = 1/n)
想请教一下大家是hashmap方法确实不能保证等概率,还是我对题目理解有偏差?到底问题出在哪里呢?谢谢大家!
|