g***j
发帖数: 1275 | 1 给一个stream of int，求当前的median
我给的答案是，用两个heap，一个min heap，一个max heap，然后keep 这两个size差
别在1以内，这样median就是两个root的某一个或者是平均值
这个题目以前没有做过，后来写code有点卡壳，还好前面写了一堆code了
哪个大侠给个code参考一下？ |
g****o
发帖数: 547 | 2 cc150上有吧
要点是你别写“两个size差别在1以内”，你写成min heap永远比max heap多一或相等
这样简单
【在 g***j 的大作中提到】
: 给一个stream of int，求当前的median
: 我给的答案是，用两个heap，一个min heap，一个max heap，然后keep 这两个size差
: 别在1以内，这样median就是两个root的某一个或者是平均值
: 这个题目以前没有做过，后来写code有点卡壳，还好前面写了一堆code了
: 哪个大侠给个code参考一下？
|
g***j
发帖数: 1275 | 3 这个不见得会简单到那儿去吧？
如果本来俩heap一样多，再来一个属于max heap，直接加就行了吧，按照你的说法，需
要move 两个点啊？
【在 g****o 的大作中提到】
: cc150上有吧
: 要点是你别写“两个size差别在1以内”，你写成min heap永远比max heap多一或相等
: 这样简单
|
c*******n
发帖数: 2764 | 4 需要保证两个性质：
1. 最小堆的最小值大于等于最大堆得最大值
2. 两个堆得大小相等或相差一 |
l****1
发帖数: 33 | 5 思路就是两个heap, max heap存放当前stream的half 较小数据, min heap
是当前stream的half较大数据。
实现不难，不过看要求了，有些细节需要考虑。
hackerrank上有这个的变种，稍难一些。 |
f*********1
发帖数: 75 | 6 一直对这个题这个解法有个疑问：
stream 是不是意味着数据量很大？两个heap 相当于存了所有的数据，这个空间复杂度
很大啊。 有没有什么优化啊？
希望大牛们不吝赐教！
【在 l****1 的大作中提到】
: 思路就是两个heap, max heap存放当前stream的half 较小数据, min heap
: 是当前stream的half较大数据。
: 实现不难，不过看要求了，有些细节需要考虑。
: hackerrank上有这个的变种，稍难一些。
|
l****1
发帖数: 33 | 7
这个很难优化，除非是用数据压缩的方法,因为理论上需要所有的数据信息。
版内有另外一题，就是引入一个window来限制空间使用:
http://www.mitbbs.com/article_t/JobHunting/32543323.html
【在 f*********1 的大作中提到】
: 一直对这个题这个解法有个疑问：
: stream 是不是意味着数据量很大？两个heap 相当于存了所有的数据，这个空间复杂度
: 很大啊。 有没有什么优化啊？
: 希望大牛们不吝赐教！
|
