📣 VIP通行证夏日特惠 限时立减$68
12
返回列表 发新帖
楼主: duangduangduang
跳转到指定楼层
上一主题 下一主题
收起左侧

狗家昂赛

🔗
idatascience 2018-5-22 01:15:23 | 只看该作者
全局:
duangduangduang 发表于 2018-5-20 05:36
我当时说BST logn找key,不过他说换了思路,比如eplison是 0.1那就以0.1为间隔建bucket, 就是你会有 0.1, ...

没太理解,那map的key如何设置可以实现O(1)的查询呢?求楼主大大解惑~
回复

使用道具 举报

🔗
 楼主| duangduangduang 2018-5-22 05:39:41 | 只看该作者
全局:
idatascience 发表于 2018-5-22 01:15
没太理解,那map的key如何设置可以实现O(1)的查询呢?求楼主大大解惑~

我回忆回忆,如果epsilon 是0.1,代表最小精度是0.1, 1/0.1 = 10, 10就是用来计算bucket的multipler

如果put(1.2, "hello") ,那就把 (1.2, "hello")这个pair放到 1.2 x 10 = 12 的bucket里面

如果要查找 get( 1.22) , 那么就去bucket 1.22 * 10 = 12的bucket 和他的两边邻居的bucket里面找( 11, 13,这个case直接在12就找到了,那么返回hello)
如果查 get(1.12), 那么就去 bucket 1.12 * 10 = 11的bucket 和他两遍邻居(10, 12)找

因为epsilon是0.1. 如果我们把每个bucket的范围限制在0.1 (方便计算,乘以multipler映射成整数),那么我们知道符合结果的key如果存在,那么一定在他整数映射的bucket或者他两遍的邻居里面。

补充内容 (2018-5-22 05:41):
输入法血崩,两边的邻居,意会下吧

评分

参与人数 2大米 +6 收起 理由
idatascience + 5 给你点个赞!
ushergod + 1 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
huangya2 2018-6-1 13:38:11 | 只看该作者
本楼:
全局:
楼主加油!
回复

使用道具 举报

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

本版积分规则

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