Question

20个有序数组，每个数组有500个数字，取出这10000个数字中最大的500个，怎么做？

20个有序数组，每个数组有500个数字，数字类型是32位uint数值，降序排列，现在需要取出这10000个数字中最大的500个，怎么做？

Answer 1

使用链表，长度是500个，把第一个数组的数据存到链表中，剩余的数组，中每个数字取出来，从头到尾比较，如果比当前值大，把链表尾部的结点摘下来，赋值为新值，插入到链表。最后剩下的就是最大的500个

Answer 2

因为是降序，我们可以直接比较每个数组中最大的，每一次去除一个最大的加入
更简单的方法是把他们全都放在一起拍个序，取前500

Answer 3

从20个数组中各取一个数，并记录每个数的来源数组，建立一个含20个元素的大根堆。
此时堆顶就是最大的数，取出堆顶元素，并从堆顶元素的来源数组中取下一个数加入堆，再取最大值，一直这样进行500次即可。
时间复杂度：500*log2(20)

追问

怎么记录每个数的来源数组？

追答

用结构体记录，一个成员记录值，一个记录来源，按成员值比较

Answer 4

要是C++就直接使用STL的堆排序。
make_heap, pop_heap
够用了。

追问

可不可以再详细点，我没怎么用过STL模版，多谢！！！

追答

还要怎么详细呢？这已经很详细了。写代码什么都说清楚了就没意思了。
如果不知道堆的性质可以回去看看数据结构。