|
|---|
|
|
|
|
|
|
S********e
发帖数: 74 | 1 Find the 90th percentile of a stream of numbers between 1 and 10^6.
Followup: What if there is not enough memory to store all numbers and no
upper bound.
从careercup上看到的，感觉第一部分用segment tree或者分成两个heap可以解决。
主要是follow up 不知道怎么弄，大家有什么思路马？ | s**********k
发帖数: 88 | 2 这个题和那个在很多数据里找median是一个思路
关于第一部分，可以在内存里放one million个counter
第二部分可以分段读入内存，不断缩小搜索范围
【在 S********e 的大作中提到】
: Find the 90th percentile of a stream of numbers between 1 and 10^6.
: Followup: What if there is not enough memory to store all numbers and no
: upper bound.
: 从careercup上看到的，感觉第一部分用segment tree或者分成两个heap可以解决。
: 主要是follow up 不知道怎么弄，大家有什么思路马？
| t*******d
发帖数: 30 | 3 不好意思，第二部分没看懂，能再讲清楚一些么？谢谢
【在 s**********k 的大作中提到】
: 这个题和那个在很多数据里找median是一个思路
: 关于第一部分，可以在内存里放one million个counter
: 第二部分可以分段读入内存，不断缩小搜索范围
|
|
|
|
|
|
|
