Google onsite难题求解，回答就加米~~

joezie · 2019-10-23 05:27:23

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

燧日岚烟 · 2019-10-23 05:36:28

joezie 发表于 2019-10-23 05:27
感谢你的回复！有几个问题想问一下：
1. 你的window 里面是只存提出了头5%和尾5%之后剩下的90%中间的值 ...

1. 是的
2. heap可以无限大，但是最小是k*5%。多出来的是old Value, pop出来以后可以删去

joezie · 2019-10-23 05:38:59

novnocturne90 发表于 2019-10-23 05:17
我还是不太懂。比如说

k = 100, k的5%是5，也就是两个heap理想情况下size是5

噢你说得对！我的方法的确有问题，大佬们能不能再支支招...

joezie · 2019-10-23 05:40:52

燧日岚烟发表于 2019-10-23 05:36
1. 是的
2. heap可以无限大，但是最小是k*5%。多出来的是old Value, pop出来以后可以删去

谢谢！另外请问可以看看这栋楼里@novnocturne90 问的问题么？你的方法具体是怎么解决这个问题的呢？

joezie · 2019-10-23 05:41:53

xiaoming2019 发表于 2019-10-23 04:26
平衡二叉树（bbst）也可以搞。一个bbst用来维护sliding window中的数，query一下max 5%和min 5%，相当于bbs ...

请问还可以看看这栋楼里@novnocturne90 问的问题么？麻烦你了~

joezie · 2019-10-23 05:42:17

snowmelt 发表于 2019-10-23 04:17
比较好想的是红黑树，维护和取都可以O(logn)。
楼上说的线段树也可以，不过如果我没理解错的话这个可能要 ...

请问还可以看看这栋楼里@novnocturne90 问的问题么？麻烦你了~

novnocturne90 · 2019-10-23 08:15:49

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

joezie · 2019-10-23 09:57:54

novnocturne90 发表于 2019-10-23 08:15
回答我自己的问题

我觉得这个题如果真的一定要用heap来做的话，是不是需要4个heap而不是之前的2个heap ...

哇你回答的好认真啊，给你点个大大的赞！！

wsha8 · 2019-10-24 01:08:10

感觉红黑树就可以了，好写好改，基本上能用priority_queue的题目都可以用红黑树写

akira2551 · 2019-10-24 04:17:32

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式