c******5
发帖数: 84 | 1 Median of Integer Stream
Given a stream of unsorted integers, find the median element in sorted
order at any given time.
So, we will be receiving a continuous stream of numbers in some random
order and we don’t know the stream length in advance.
Write a function that finds the median of the already received numbers
efficiently at any time. We will be asked to find the median multiple times.
Just to recall, median is the middle element in an odd length sorted array,
and in the even case it’s the average of the middle elements. | t**v
发帖数: 101 | 2 what is their answer ? I can only think of hash table. O(n)
times.
array,
【在 c******5 的大作中提到】
: Median of Integer Stream
: Given a stream of unsorted integers, find the median element in sorted
: order at any given time.
: So, we will be receiving a continuous stream of numbers in some random
: order and we don’t know the stream length in advance.
: Write a function that finds the median of the already received numbers
: efficiently at any time. We will be asked to find the median multiple times.
: Just to recall, median is the middle element in an odd length sorted array,
: and in the even case it’s the average of the middle elements.
| c******5
发帖数: 84 | 3 I think their answer should be maintain a max-heap which stores the lower
half values and a min-heap which stores the upper half values. Here are the
details for this solution:
http://www.ardendertat.com/2011/11/03/programming-interview-que
【在 t**v 的大作中提到】
: what is their answer ? I can only think of hash table. O(n)
:
: times.
: array,
|
|
