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

shuatijeff 发表于 2019-10-24 11:11
是不是可以用 BIT 保存k个值，用来计算和， 然后 用quick select 来找前后的5%， 然后 用 BIT 的和减 找到 ...

quickselect k 需要O(n)时间

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

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

燧日岚烟 发表于 2019-10-23 04:48
一个map存，一个map存window里。
1. check oldValue in heap. If so, count+1 on oldValue map. If not, c ...

请问你这个可以实现更新比平均 O(logn)还好吗?

ronaldo123 发表于 2019-11-26 07:59
请问你这个可以实现更新比平均 O(logn)还好吗?

这就是O(logn)的解法啊

燧日岚烟 发表于 2019-11-26 10:16
这就是O(logn)的解法啊

看来目前讨论的方案最好的就是logn了

新人一枚，如果觉得我的思路合理求送米， 揭不开锅了， 谢谢大家。

我觉得我们把这个问题复杂化了。 因为是streaming data，可以用 插入排序 得到一个大小为k的有序数组， 可以简单地去除掉前后5%，还需要维护一个中间90%的sum， 方便求平均值。 最重要sliding window， 出界的话用binary search 方法从有序数组中去掉， 再sum 减掉这个数。

eraser 发表于 2019/12/31 17:00:56
新人一枚，如果觉得我的思路合理求送米， 揭不开锅了， 谢谢大家。

我觉得我们把这个问题复杂化了。 因为是strea...

感谢你的分享！那请问你要用什么数据结构来存这个大小为k的数组，从而得以保证删除旧值的操作是小于O（n）的呢？

eraser 发表于 2019/12/31 17:00:56
新人一枚，如果觉得我的思路合理求送米， 揭不开锅了， 谢谢大家。

我觉得我们把这个问题复杂化了。 因为是strea...

感谢你的分享？那请问你要用什么数据结构来存这个大小为k的数组，从而可以保证删除旧值的操作是小于O（n）的呢？