Given a stream of unsorted integers, find the median element in sorted order at any given time

http://www.ardendertat.com/2011/11/03/programming-interview-questions-13-median-of-integer-stream/

http://codercareer.blogspot.com/2012/01/no-30-median-in-stream.html

相似的online algorithm:

http://www.geeksforgeeks.org/reservoir-sampling/

取样问题:从未知总数的元素中选择一个

  从事先未知总数为n的对象中随机选择一个的方法。有两种常见的具体问题:

  1.读取一个未知行数的文件,随机输出其中的的一行,同时最多只能缓冲一行的内容(《编程珠玑(续)》习题15.3利用了这种形式);

  2.对链表进行一趟遍历,随机输出其中的一个结点的元素,只能使用一个临时指针。

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s