AVG of last K elements, 去掉最大和最小的5%

LC上看到别人讨论这个题，
是一个stream
需要输出 最后K个数的平均值，但是需要去掉这K个数里面最大和最小的5%。

求思路

lyronly 发表于 2019-11-26 07:34
binary indexed tree 怎么去掉最大5% 和最小5%？

2个BIT一个记录cumulative sum 一个记录个数, 二分搜索查找percentile.. 不知道你对BIT了解多少

337845818 发表于 2019/11/24 23:47:47
树状数组了解一下。。。

binary indexed tree 怎么去掉最大5% 和最小5%？

重点应该是怎么去有效率地维护最大值和最小值
用两个priority_queue分别维护最大值和最小值
存储的时候考虑存储值以及序号（即pair<value, index>）。在每次求最大/最小值时，检查index是否在有效范围（即最近的K元素的index范围内），如果不是则pop元素再看下一个top元素。

shirochan 发表于 2019-11-21 10:15
重点应该是怎么去有效率地维护最大值和最小值
用两个priority_queue分别维护最大值和最小值
存储的时候考 ...

所以复杂度的是 O(N*K*Log(N)) 么?

树状数组了解一下。。。

lyronly 发表于 2019-11-26 07:34
binary indexed tree 怎么去掉最大5% 和最小5%？

我也表示怀疑，懒得问了。

是谷歌的onsite面经吧，地里很多讨论贴吧