703. 数据流中的第 K 大元素
2024-09-04 07:12:52
设计一个找到数据流中第 K 大元素的类（class）。注意是排序后的第 K 大元素，不是第 K 个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组 nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第 K 大的元素。
示例:
int k = 3;
int[] arr = [4,5,8,2];
KthLargest kthLargest = new KthLargest(3, arr);
kthLargest.add(3); // returns 4
kthLargest.add(5); // returns 5
kthLargest.add(10); // returns 5
kthLargest.add(9); // returns 8
kthLargest.add(4); // returns 8
说明:
你可以假设 nums 的长度≥ k-1 且 k ≥ 1。
解答：维护一个大根堆和一个小根堆，小根堆存放最大的K-1个元素，大根堆存放剩余的元素。当小根堆放入第K个元素后，取出小根堆堆顶元素放入大根堆。因此小根堆内元素个数永远是k-1，大根堆的堆顶元素就是我们要的第K大元素
class KthLargest {
private PriorityQueue<Integer> bigHeap;
private PriorityQueue<Integer> smaHeap;
public KthLargest(int k, int[] nums) {
bigHeap = new PriorityQueue<>((o1,o2)->o2.compareTo(o1));
smaHeap = new PriorityQueue<>((o1,o2)->o1.compareTo(o2));
for(int i=0;i<k-1;i++){
smaHeap.offer(nums[i]);
}
for(int i=k-1;i<nums.length;i++){
smaHeap.offer(nums[i]);
bigHeap.offer(smaHeap.poll());
}
}
public int add(int val) {
smaHeap.offer(val);
bigHeap.offer(smaHeap.poll());
return bigHeap.peek();
}
}
最新文章
- DrawerLayout的使用
- PHP读文件的一个乱码问题
- FreeMarker笔记 前言&第1章 入门
- hadoop2的automatic HA+Federation+Yarn配置的教程
- Android_PendingIntent的使用
- 嵌入式Linux系统运行流程图
- O、Ω、Θ表示
- ESP8266固件修改可以控制多个IO方法
- [转]lftp的致命错误：证书验证：不信任
- Sublime Text 3 全程详细图文原创教程
- tomcat+nginx实现
- h5+js视频播放器控件
- input标签（文本域和文件域）
- WORDPRESS修改文章文件后，出现乱码
- java 获取 path
- bat脚本自动备份文件资源
- FisherYates费雪耶兹随机置乱算法
- http://blog.csdn.net/steveguoshao/article/details/38414145
- 新型智能芯片nxp----嗯质朴
- Android View体系 系列文章