Find the median from a stream of integers

user_171230 0
Viewed 8088

Given an unsorted sequence of integers that flows into your program as a stream.

The integers are too many to fit into memory.

Imagine there is a function:

int getNext() throws NoSuchElementException;

It returns the next integer from the stream.

Write a function to find the median.

Solve the problem in O(n).

Any ideas?

Hint is given (use heap the data structure..)

algorithm
4 Answers

Suppose the window for the median to maintain is K. Construct a binary search tree for K number. O(K); Do in-order traversal and find the (K/2)th element.O(K/2);

The overall time is O(K).

user_7898460
Related