📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
12
返回列表 发新帖
楼主: milanelllo13
跳转到指定楼层
上一主题 下一主题
收起左侧

[学Java/C#] 分享一个昨天被三哥黑的题。。。

🔗
wangxinlei 2015-7-4 14:26:01 | 只看该作者
全局:
楼主面的是不是H打头的那家?因为我也是被问到这个题。。
回复

使用道具 举报

🔗
 楼主| milanelllo13 2015-7-4 14:30:02 | 只看该作者
全局:
wangxinlei 发表于 2015-7-4 14:26
楼主面的是不是H打头的那家?因为我也是被问到这个题。。

是啊。。 你感觉是被被黑了吗。。。
回复

使用道具 举报

🔗
wangxinlei 2015-7-4 23:17:59 | 只看该作者
全局:
必须是啊,阿三全程啃手指玩手机。。。或者他们是要找更牛逼的人?
回复

使用道具 举报

🔗
 楼主| milanelllo13 2015-7-5 02:42:35 | 只看该作者
全局:
wangxinlei 发表于 2015-7-4 23:17
必须是啊,阿三全程啃手指玩手机。。。或者他们是要找更牛逼的人?

我狭隘的认为他想找个印度人。。。
回复

使用道具 举报

🔗
handsomecool 2015-7-5 06:25:33 | 只看该作者
全局:
应该是interval tree了, 支持log(n)的各种操作 , interval tree本身不难但没学过要现场想就好难啊我感觉。。。 我就没学过,刷题才偶然接触到的,还觉得一定不会考呢。。 ╮(╯_╰)╭
回复

使用道具 举报

🔗
handsomecool 2015-7-5 12:24:22 | 只看该作者
全局:
本帖最后由 handsomecool 于 2015-7-5 12:34 编辑

呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更小的闭区间,以区间开始为key用BST结构去存,并记录下每个区间对应的原区间的ID。
1 {1, 3},2 {2, 10},3 {3, 2^26} 就变成了:

Interval ----------------------------ID
[1,   1]                                   1
[2,   2]                                   1, 2
[3,   3]                                   1, 2, 3
[4,  10]                                  2, 3
[11, 2^26]                             3


然后如果你要删掉含有2的interval, 只要log(n)的时间(因为用了BST) 就可以找到它所在的区间[2, 2] 然后删掉对应的ID 1 和 2 。
如果还要删掉细分后的Interval里对应的ID就比较麻烦了, 而且如果Interval的ID删完变空了,那个Interval就直接不要了, 所以还要个map来存ID反过来对应了哪些细分的Interval, 比如ID 2:{2, 3, 4}  (这里的 2, 3, 4 是细分Interval的key)...
下图的红色部分是删掉的。

Interval ----------------------------ID
[1,   1]                                   1
[2,   2]                                   1, 2

[3,   3]                                   1, 2, 3
[4,  10]                                  2, 3
[11, 2^26]                             3


也可以不删掉细分后的interval, 给每个ID存一个是否已经被删除的flag, 这样就简单多了。
回复

使用道具 举报

🔗
 楼主| milanelllo13 2015-7-5 13:17:33 | 只看该作者
全局:
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

我觉得这样做是对的!
回复

使用道具 举报

🔗
 楼主| milanelllo13 2015-7-5 13:23:34 | 只看该作者
全局:
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

感谢分享解法! ~
回复

使用道具 举报

🔗
stellari 2015-7-5 14:09:41 | 只看该作者
全局:
handsomecool 发表于 2015-7-5 12:24
呃。。。又想了想,貌似有不用interval tree的做法。。。
Insert的时候通过取交集把这些interval细分成更 ...

这其实就是“离散化的线段树(segment tree)”吧。这种方法可以,但是插入时间似乎会比较长,比如如果某时刻加入了一个很长的interval,覆盖了之前的所有interval,那么之前每个Interval对应的ID就必须更新,这是一个O(N)操作。查找+删除依然是O(logN + N)操作,和Interval Tree一样。但是Interval Tree的插入时间是O(logN),这点应该是优于此方法的。
回复

使用道具 举报

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

本版积分规则

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