当前位置 博文首页 > qq_41603622的博客：面试常见问题之TopK
在面试中，topk问题是经常被问到的一类问题，形如:
从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
这种问题其实有很多种解法，最容易想到的就是排序，取出前K个最大的值。因为最近学了优先级队列(堆)，这里主要利用创建堆的方式求解topk问题。堆是什么就不具体介绍了，看一看概念就可以了
- 堆逻辑上是一棵完全二叉树
- 堆物理上是保存在数组中
- 满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆。 反之，则是小堆，或者小根堆，或者最小堆
- 堆的基本作用是，快速找集合中的最值
另外需要注意的是：
1.求前k个最大创建小堆，求前k个最小创建大堆
2.只找到TopK，不排序TopK。
这里我们就以求前k个最大为例（问题看起来高大上，代码其实很简单）：
思路
1.创建一个大小为k的小堆.
2.遍历数组，将前k个元素放入小堆中.
3.从第k+1个元素开始，与堆顶进行比较，如果比堆顶大，就 先出 后入.
import java.util.Comparator;
import java.util.PriorityQueue;
/**
* ClassName: TopK
* Description:topk问题
* date: 2021/5/11 21:18
* @author wt
* @since JDK 1.8
*/
public class TopK {
/**
* 前K个最大的
* 思路:
* 1.创建一个大小为K的小堆
* 2.遍历数组，将前K个元素放入小队中
* 3.从第k+1个元素开始，与 堆顶元素比较
* 4.当前元素比堆大，那么，先出 后入
*/
public static void topK(int[] array,int k) {
//创建一个大小为k的小堆，priorityQueue默认为小堆，继承Comparator接口重写compare方法可以改为大堆
PriorityQueue<Integer> minTopK = new PriorityQueue<>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o1-o2;
}
});
for (int i = 0; i<array.length ;i++) {
if (k>0) {
minTopK.offer(array[i]);//前k个元素入堆
k--;
} else {
Integer top = minTopK.peek();
if (top < array[i]) {
minTopK.poll();//先出
minTopK.offer(array[i]);//后入
}
}
}
System.out.println(minTopK);
}
public static void main(String[] args) {
int[] array = {3,6,77,88,99,22,34,545,543,32,45,111,3434};
topK(array,3);
}
}
测试结果就不放了，写博客主要的还是防止自己搞忘了知识点，记录一下，好查询
cs