leetcode刷题（42）——703. 数据流中的第K大元素
leetcode刷题（42）——703. 数据流中的第K大元素
老马的编程之旅
发布于 2022-06-22 13:35:52
发布于 2022-06-22 13:35:52
代码可运行
运行总次数：0
代码可运行
设计一个找到数据流中第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。
题解： 关于 Java 的 PriorityQueue 优先级队列 1 是线程不安全的队列 2 存储使用数组实现 3 利用比较器做优先级比较
实现说明 1 最小堆的特性就是最小的值在最上面，每次取O(1)，插入O(n) 2 初始化的时候，注意如何添加元素，并给队列一个合适大小的初值 3 每次添加元素，能添加到队列的有两种情况，一种未到k个，另一种比堆顶大
PriorityQueue默认实现就是可以支持最小堆，因为他的默认排序方式就是从小到达排序
class KthLargest {
private PriorityQueue<Integer> queue;
private int limit;
public KthLargest(int k, int[] nums) {
queue = new PriorityQueue(k);
limit = k;
for(int i=0;i<nums.length;i++){
add(nums[i]);
}
}
public int add(int val) {
if(queue.size()<limit){
queue.add(val);
}else if(queue.peek()<val){
queue.poll();
queue.add(val);
}
return queue.peek();
}
}
/**
* Your KthLargest object will be instantiated and called as such:
* KthLargest obj = new KthLargest(k, nums);
* int param_1 = obj.add(val);
*/本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2020-01-25，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
