想讨论一道谷歌高频题

有个思路。实际生产中不需要特别精确的值。如果数据满足某种概率分布，可以估算一个上下边界。计算输出平均值的时候直接抛弃边界外的值。

WIwindson 发表于 2020-2-21 14:20
你不需要从树或者最大最小堆中删除旧的无效的元素吗？

比如前100个数都是10，然后来200个1，那么之前在5%里的10就会回到中间部分了吧。如果再后面有很多的100，10又有会再度进入5%范围了。如果把10抛弃了，结果是不是就不对了？

求大佬解惑。

joe297 发表于 2020-2-7 07:09
开一个BST，维护一个mean，total number of integers，number of integers in BST
每有一个新integer，进 ...

看了半天，就你这个方法最简洁！有效！
而且用标准库的结构(Set, Treeset)就能搞定，不需要modify红黑树记录子树节点个数与和。

原本我想的方法是开一个BST，维护5%、95% quantile的Iterator
看了你的答案才意识到上下5%的信息我们并不需要了
Brilliant！


放进disk。。会考这么难吗？

intelliu 发表于 2020-1-22 02:54
有人想过只存最大的5%和最小的5%吗， 这样可以省下很多空间， 然后用总数减去这部分的和再除以元素个数就能 ...

某一阶段5%对应50个元素，堆的大小是50，如果后来堆的大小变大了，应该让哪个元素进去呢？ （如果不存中间部分，似乎难以知道）

joe297 发表于 2020-2-7 07:09
开一个BST，维护一个mean，total number of integers，number of integers in BST
每有一个新integer，进 ...

哦不好意思，之前看到你的答案，以为前5%和后5%的信息可以不管。
后来想想不可以，因为新数据进来时，BST不止可能删最大最小，可能还得额外加进比最大/最小 更大/更小的数。

我觉得还是需要把全部数据存进BST，并把5%, 95% quantile的iterator存好

这个是利口 尾巴而无 吗？