查看: 570| 回复: 0
跳转到指定楼层
上一主题 下一主题
收起左侧

[Leetcode] Leetcode710. Random Pick with Blacklist 的Hashmap解法的概率疑问

🔗
匿名用户-MLF5W  2022-3-8 20:53:34 |倒序浏览

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

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方法确实不能保证等概率,还是我对题目理解有偏差?到底问题出在哪里呢?谢谢大家!


上一篇:「刷題小白-Java」分享一下我的學習資源/刷題順序 干貨
下一篇:哪家公司的高频和面经比较有用
您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表