【面试必备】如何在10亿数中找出前1000大的数?

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。

之前小史在BAT三家的面试中已经挂了两家，今天小史去了BAT中的最后一家面试了。

简单的自我介绍后，面试官给了小史一个问题。

【面试现场】

题目：如何在10亿数中找出前1000大的数？

小史：我可以用分治法，这有点类似快排中partition的操作。随机选一个数t，然后对整个数组进行partition，会得到两部分，前一部分的数都大于t，后一部分的数都小于t。

小史：如果说前一部分总数大于1000个，那就继续在前一部分进行partition寻找。如果前一部分的数小于1000个，那就在后一部分再进行partition，寻找剩下的数。

小史：首先，partition的过程，时间是o(n)。我们在进行第一次partition的时候需要花费n，第二次partition的时候，数据量减半了，所以只要花费n/2，同理第三次的时候只要花费n/4，以此类推。而n+n/2+n/4+...显然是小于2n的，所以这个方法的渐进时间只有o(n)

（注：这里的时间复杂度计算只是简化计算版，真正严谨的数学证明可以参考算法导论相关分析。）

半分钟过去了。

小史一时慌了神。

他回忆起了之前吕老师给他讲解bitmap时的一些细节。突然有了一个想法。

小史在纸上画了画。

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

TopN.java

Main.java

运行结果：

面试官看了一下。

小史熟练地介绍起了自己的项目，由于准备充分，小史聊起来游刃有余。面试官问的几个问题也进行了详细的解释。

小史走后，面试官在系统中写下了面试评语：

【遇见吕老师】

小史回到学校哼着歌走在校园的路上，正好碰到吕老师。

小史把面试情况和吕老师说了一下。

小史：感悟还挺深的。虽然平时做过topN的问题，知道分治法时间更少。但是碰到具体问题的时候还是要具体分析，这种大数据量的情况下反而用堆会更快。