如何找出排名前500的数？

文档摘要

如何找出排名前 500 的数？题目描述有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20\500 个数中找出前 500 的数？解答思路对于 TopK 问题，最常用的方法是使用堆排序。对本题而言，假设数组降序排列，可以采用以下方法：首先建立大顶堆，堆的大小为数组的个数，即为 20，把每个数组最大的值存到堆中。接着删除堆顶元素，保存到另一个大小为 500 的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。重复上面的步骤，直到删除完第 500 个元素，也即找出了最大的前 500 个数。为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法。