c*********h
发帖数: 102 | 1 原题在这里：
http://www.geeksforgeeks.org/median-of-stream-of-integers-runni
Given that integers are read from a data stream. Find median of elements
read so for in efficient way. For simplicity assume there are no duplicates.
For example, let us consider the stream 5, 15, 1, 3 …
After reading 1st element of stream - 5 -> median - 5
After reading 2nd element of stream - 5, 15 -> median - 10
After reading 3rd element of stream - 5, 15, 1 -> median - 5
After reading 4th element of stream - 5, 15, 1, 3 -> median - 4, so on...
每新进一个数，就binary search放进sorted array，记录一个录入几个数；取中间一
个或中间两个平均就是；时间复杂度对第n的进来的数就是O（nlogn）。
用两个heap做，难道不是一样的吗？每次heapify不就是个二查的过程吗？如果你非要
说heapify 的tighter bound is O(n) and upper bound is O(n log n)；那同样情况
的binary sort的tighter bound也是O(n)啊。
高手请指教！多谢！！！ | m**p
发帖数: 189 | | c*********h
发帖数: 102 | 3 什么意思？如果考虑space，heap不是也一样？
【在 m**p 的大作中提到】
: 那你的数组无穷大了？
| c********6
发帖数: 33 | 4 那用什么存放数呢？
如果要支持插入的话就得是链表或动态数组
链表没法二分查找吧，寻找时o(n)
动态数组到时可是二分，但是插入得o(n) | f*******w
发帖数: 1243 | 5 你怎么insert到array里？Worst case是O(n). |
|
