分类 Java面试题 下的文章

对于海量数据到处理经常会涉及到 topK 问题。在设计数据结构和算法的时候,主要需要考虑的应该是当前算法(包括数据结构)跟给定情境(比如数据量级、数据类型)的适配程度,和当前问题最核心的瓶颈(如降低时间复杂度,还是降低空间复杂度)是什么。首先,我们来举几个常见的 topK 问题的例子:

- 阅读剩余部分 -

题目描述有 20 个数组,每个数组有 500 个元素,并且有序排列。如何在这 20*500 个数中找出前 500 的数?解答思路对于 TopK 问题,最常用的方法是使用堆排序。对本题而言,假设数组降序排列,可以采用以下方法:首先建立大顶堆,堆的大小为数组的个数,即为 20,把每个数组最大的值存到堆中。接着删除堆顶元素,保存到另一个大小为 500 的数组中,然后向大顶堆插入删除的元素所在数组的下一个元素。

- 阅读剩余部分 -