【百度笔试题】找出最大的500个数

从一个师弟那里得到一个百度的笔试题：

有10000个数，分成20组（m），每组500个（n），按倒序排列，请设计一个算法，找出这10000个数最大的500个。

如果把题目简化一下，是两组，那么这个题就简单了，考察的就是一个归并排序了，那复杂度就是O(n)了。其实对于20组可以利用同样的思路。

把这20组树表示为：
X1,1 X1,2 … X1,n
X2,1 X2,2 … X2,n
…
Xm,1 Xm,2 … Xm,n

首先将X1,1 X2,1 … Xm,1排序，复杂度为O(mlgm)，这样就可以找到这批数据中的最大值，比如为Xk,1，那么最大的那个数位Xk,1，然后我们可以把Xk,1删除，然后把Xk,2插入到适当的位置，这样又可以删除最大的数，重复此过程，直到找到最大的n个数。把一个数插入到合适的位置的时间复杂度为O(m)，那么总的时间复杂度为O(mlgm) + O(mn)。

后来想想可以利用堆来加速，开始将X1,1 X2,1 … Xm,1调整成大顶堆，时间复杂度为O(m)，删除堆顶，比如为Xk,1，那替换为Xk,2，调整为大顶堆，时间复杂度为O(lgm)，重复此过程，直到找到最大的n个数。总共的时间复杂度为O(m) + O(nlgm)。