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

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即刻解锁阅读权限或查看其他获取积分的方式

joezie · 2019-10-24 04:32:03

wsha8 发表于 2019/10/24 01:08:10
感觉红黑树就可以了，好写好改，基本上能用priority_queue的题目都可以用红黑树写

可是面试的时候真的有时间写红黑树么…

wsha8 · 2019-10-24 04:37:20

joezie 发表于 2019/10/24 04:32:03
可是面试的时候真的有时间写红黑树么…

你猜猜TreeMap是怎么实现的，就是要处理重复，但是不是太难

我用的c艹，这个有multimap，解这个问题更加方便，

wsha8 · 2019-10-24 04:43:48

itgoujie2 发表于 2019/10/23 04:01:07
能不能把maxHeap和minHeap的大小定义成k+5%

可以是可以，但是问题是我们怎么知道哪些元素在那5%里面

itgoujie2 · 2019-10-24 09:36:42

wsha8 发表于 2019/10/24 04:43:48
可以是可以，但是问题是我们怎么知道哪些元素在那5%里面

那可能我理解错了，我以为这个数据流是会结束的，只要结束之后再poll5%就好了

shuatijeff · 2019-10-24 11:11:13

是不是可以用 BIT 保存k个值，用来计算和，然后用quick select 来找前后的5%，然后用 BIT 的和减找到了值，然后求平均，

krystal1115 · 2019-10-25 15:36:35

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