如何在 10 亿数中找出前 1000 大的数
作者 | channingbreeze
来源 | 互联网侦察
小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进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 时的一些细节。突然有了一个想法。
小史在纸上画了画。
理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：
/**
* @author xiaoshi on 2018/10/14.
*/
public class TopN {
// 父节点
private int parent(int n) {
return (n - 1) / 2;
}
// 左孩子
private int left(int n) {
return 2 * n + 1;
}
// 右孩子
private int right(int n) {
return 2 * n + 2;
}
// 构建堆
private void buildHeap(int n, int[] data) {
for(int i = 1; i < n; i++) {
int t = i;
// 调整堆
while(t != 0 && data[parent(t)] > data[t]) {
int temp = data[t];
data[t] = data[parent(t)];
data[parent(t)] = temp;
t = parent(t);
}
}
}
// 调整data[i]
private void adjust(int i, int n, int[] data) {
if(data[i] <= data[0]) {
return;
}
// 置换堆顶
int temp = data[i];
data[i] = data[0];
data[0] = temp;
// 调整堆顶
int t = 0;
while( (left(t) < n && data[t] > data[left(t)])
|| (right(t) < n && data[t] > data[right(t)]) ) {
if(right(t) < n && data[right(t)] < data[left(t)]) {
// 右孩子更小，置换右孩子
temp = data[t];
data[t] = data[right(t)];
data[right(t)] = temp;
t = right(t);
} else {
// 否则置换左孩子
temp = data[t];
data[t] = data[left(t)];
data[left(t)] = temp;
t = left(t);
}
}
}
// 寻找topN，该方法改变data，将topN排到最前面
public void findTopN(int n, int[] data) {
// 先构建n个数的小顶堆
buildHeap(n, data);
// n往后的数进行调整
for(int i = n; i < data.length; i++) {
adjust(i, n, data);
}
}
// 打印数组
public void print(int[] data) {
for(int i = 0; i < data.length; i++) {
System.out.print(data[i] + " ");
}
System.out.println();
}
}
面试官看了一下。
小史熟练地介绍起了自己的项目，由于准备充分，小史聊起来游刃有余。面试官问的几个问题也进行了详细的解释。
小史走后，面试官在系统中写下了面试评语：
【遇见吕老师】
小史回到学校哼着歌走在校园的路上，正好碰到吕老师。
小史把面试情况和吕老师说了一下。
小史：感悟还挺深的。虽然平时做过 topN 的问题，知道分治法时间更少。但是碰到具体问题的时候还是要具体分析，这种大数据量的情况下反而用堆会更快。
