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大的值
}
}
}

最新文章

  1. httplib用法
  2. yum命令——安装、卸载、查询等
  3. 高性能网站架构设计之缓存篇(2)- Redis C#客户端
  4. python-generator生成杨辉三角
  5. SSH 创建证书认证
  6. startUML常用的组合片段
  7. 试验Windows Embedded Standard 7 Service Pack 1 Evaluation Edition
  8. ZStack之ZDApp_Init解析
  9. Nunit中文文档
  10. a标签的背景图在ie8下显示问题
  11. C++发送邮件和附件
  12. Ubuntu 14.04 64位安装Android Studio 和 genymotion (上)
  13. 理解 Objective-C Runtime
  14. abap 增强查找小程序
  15. 给django视图类添加装饰器
  16. 关于 lua table表存储函数且运用
  17. 第二篇 Flask 中的 Render Redirect HttpResponse
  18. day16 Python map函数
  19. asp.net core配置文件
  20. 使用sigaction函数

热门文章

  1. 2 - Rich feature hierarchies for accurate object detection and semantic segmentation(阅读翻译)
  2. pl/sql Developer连接oracle远程数据库
  3. 内部排序总结之----插入类排序(插入和Shell)
  4. 图书管理(单链表C++)
  5. DDCTF-2019-writeup(7web+5misc)
  6. PHP-生产随机验证码图片
  7. 【log4j】log4j.properties 文件示例
  8. centos 下启动 rabbitmq 报错的解决
  9. git分布式版本管理系统
  10. 从源码学习使用 node-delegates