基于PriorityQueue(优先队列)解决TOP-K问题
2024-10-06 19:41:49
TOP-K问题是面试高频题目,即在海量数据中找出最大(或最小的前k个数据),隐含条件就是内存不够容纳所有数据,所以把数据一次性读入内存,排序,再取前k条结果是不现实的。
下面我们用简单的Java8代码去解决TOP-K问题。为了使主要的逻辑更加清晰,去掉了一些如参数合法性检查等非关键代码。
PriorityQueue(优先队列)是JDK1.5开始提供的,主要作者包括大名鼎鼎的纽约大学教授Doug Lea,他也是Java JUC包的鼻祖哦。
PriorityQueue相当于一个堆(默认为小根堆,如果想要创建大根堆,那么在创建PriorityQueue时应指定为逆序,代码如下)
new PriorityQueue<>(maxSize, Comparator.reverseOrder());
下面我们就以默认的小根堆去解决TOP-K问题(小根堆用于解决前k个最大值,而大根堆用于解决前k个最小值)
class FixSizedPriorityQueue {//自定义固定长度(k)的优先队列,因此可以解决Top-k问题
PriorityQueue<Integer> queue;
int k; public FixSizedPriorityQueue(int k) {
this.k = k;
this.queue = new PriorityQueue<>(k);
} public void add(Integer e) {
if (queue.size() < k) { //当前队列元素个数不足k个时,直接添加
queue.add(e);
} else { //超出k个时
if (e.compareTo(queue.peek()) > 0) {// 如果新元素大于了堆顶元素,说明新元素应替换掉当前堆顶元素
queue.poll();
queue.add(e);
}
}
}
}
public class Main { public static void main(String[] args) { final FixSizedPriorityQueue pq = new FixSizedPriorityQueue(10);
Random random = new Random();
random.ints(100, 0, 1000).forEach(pq::add);//产生100个0-1000的随机数,并加入自定义的定长优先队列
while (!pq.queue.isEmpty()) {
System.out.print(pq.queue.poll() + ", ");//不断取出堆顶元素,由于本例是小根堆,因此会从小到大打印出前10大的值
}
}
}
最新文章
- httplib用法
- yum命令——安装、卸载、查询等
- 高性能网站架构设计之缓存篇(2)- Redis C#客户端
- python-generator生成杨辉三角
- SSH 创建证书认证
- startUML常用的组合片段
- 试验Windows Embedded Standard 7 Service Pack 1 Evaluation Edition
- ZStack之ZDApp_Init解析
- Nunit中文文档
- a标签的背景图在ie8下显示问题
- C++发送邮件和附件
- Ubuntu 14.04 64位安装Android Studio 和 genymotion (上)
- 理解 Objective-C Runtime
- abap 增强查找小程序
- 给django视图类添加装饰器
- 关于 lua table表存储函数且运用
- 第二篇 Flask 中的 Render Redirect HttpResponse
- day16 Python map函数
- asp.net core配置文件
- 使用sigaction函数
热门文章
- 2 - Rich feature hierarchies for accurate object detection and semantic segmentation(阅读翻译)
- pl/sql Developer连接oracle远程数据库
- 内部排序总结之----插入类排序(插入和Shell)
- 图书管理(单链表C++)
- DDCTF-2019-writeup(7web+5misc)
- PHP-生产随机验证码图片
- 【log4j】log4j.properties 文件示例
- centos 下启动 rabbitmq 报错的解决
- git分布式版本管理系统
- 从源码学习使用 node-delegates