发个面试时的经典题目
原贴:http://bbs.hadoopor.com/thread-138-1-1.html
现有1亿个整数均匀分布，如果要得到前1K个最大的数，求最优的算法。-
（先不考虑内存的限制，也不考虑读写外存，时间复杂度最少的算法即为最优算法）-
-
我先说下我的想法:分块，比如分1W块，每块1W个，然后分别找出每块最大值，从这最大的1W个值中找最大1K个，那么其他的9K个最大值所在的块即可扔掉，从剩下的最大的1K个值所在的块中找前1K个即可。那么原问题的规模就缩小到了1/10。-
-
问题：-
1.这种分块方法的最优时间复杂度。-
2.如何分块达到最优。比如也可分10W块，每块1000个数。则问题规模可降到原来1/100。但事实上复杂度并没降低。-
3.还有没更好更优的方法解决这个问题。-
-
希望大家来讨论讨论，踊跃提出自己的解决方式和思路。-
------解决方案--------------------

引用:

我先说下我的想法:分块，比如分1W块，每块1W个，然后分别找出每块最大值，从这最大的1W个值中找最大1K个，那么其他的9K……

楼主你的想法可能会有漏掉的，拥有最大值的那块，前面1000个数未必就是最大的1000个数

如果按分块来做，1W*1W块，需要在每一块都找到前1000个，然后对剩下的1000W个数继续分组找...
------解决方案--------------------

------解决方案--------------------
学习。。。
------解决方案--------------------
学习下喔.!
------解决方案--------------------
这个题目 搞不定啊
------解决方案--------------------
很难的一道有关数据结构的题……
------解决方案--------------------
纯粹来观摩学习！
------解决方案--------------------
的确如一楼所说，
如果某块里假设有最大的两个值，那么用楼主的方法去取不到第二个大值的。
所以楼主的结果页肯定是错误的！
------解决方案--------------------
这个题目 搞不定啊
------解决方案--------------------
堆 Or 二叉树的插入。