百度面试-求多个有序数组中前n的最大值

百度面试原题如下：有20个数组，每个数组里面有500个数组，降序排列，每个数字是32位的unit,求出这10000个数字中最大的500个。

无意间浏览到这题百度面试题贴，下面各路大神解答百度面试题。但是其中的这题基本都是用归并排序办法求，最好的也就是用min_heep。看到后感觉他们提到的这些算法没有对数组有序这个条件很好的利用，以下算法是我解答这题的愚见，如有问题请批评指正。

我把这题推广到一个类型：有n个数组，每个数组里面有m个数组，降序排列，每个数字是32位的unit,求出这m*n个数字中最大的k个。

我们先思考一个问题有两个数组 a1[m]，a2[m],我们求这两个数组中最大的k个值

那么我们假设a1中前x1个数属于最大的k个值，a2中前x2个数输入最大的k值

那么x1+x2 = k；如图

由此我们可以得出x1和x2中肯定有一个大于等于k/2,怎么确定呢，我们只需比较a1[k/2]和a2[k/2]谁大那么就说么谁大于k/2;那么我们就直接把他的前k/2取出来。剩下的我们就递归取出就ok了，每次我们可以去除剩下的1/n个，（比较k/n时你可能碰到有的数组被取完了或者不够k/n自己稍加处理即可）测试程序

#include <iostream>
using namespace std;
int main()
{

int n, m, k, icount;
//有n个数组，每个数组里面有m个数组，降序排列，每个数字是32位的unit,求出这m*n个数字中最大的k个。
while (cin >> n >> m>> k)
{
icount = 0;
while (k >=n)
{
cout<<"查找出"<<k/n<<"个最大值还剩下最大值个数为"<<k-k/n<<endl;
k = k-k/n;
icount+=n;
}
cout<<"共查找"<<icount<<"次"<<endl;

}
return 0;
}

比归并排序快乐将近6倍 。当k/n越大时查找的效率越高