如何找出排名前500的数？

Nen 2021-10-08 11:20

- 程序员

分析解答：对于求top k的问题，最常用的方法为堆排序方法。对于本题而言，假设数组降序排列，可以采用如下方法：

（1）首先建立大顶堆，堆的大小为数组的个数，即20，把每个数组最大的值（数组第一个值）存放到堆中。

（2）接着删除堆顶元素，保存到另外一个大小为500的数组中，然后向大顶堆插入删除的元素所在数组的下一个元素。

（3）重复第（1）、（2）步骤，直到删除个数为最大的k个数，这里为500。为了在堆中取出一个数据后，能知道它是从哪个数组中取出的，从而可以从这个数组中取下一个值，可以把数组的指针存放到堆中，对这个指针提供比较大小的方法（比较指针指向的值）。为了便于理解，把题目进行简化：三个数组，每个数组有5个元素且有序，找出排名前5的数。

程序的运行结果为

30 29 25 20 19

通过把ROWS改成20，COLS改成50，并构造相应的数组，就能实现题目的要求。对于降序排列的数组，实现方式类似，只不过是从数组的最后一个元素开始遍历。

轩辕小不懂的其他提问

类似问题

如何找出排名前500的数？

轩辕小不懂 的其他提问

类似问题

轩辕小不懂的其他提问