内容简介：版权声明： 本文为博主原创文章，发表自知一的指纹。转载需向设计一个找到数据流中第K大元素的类（class）。注意是排序后的第K大元素，不是第K个不同的元素。你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
版权声明： 本文为博主原创文章，发表自知一的指纹。转载需向 我的邮箱 申请。
设计一个找到数据流中第K大元素的类（class）。注意是 排序 后的第K大元素，不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器，它包含数据流中的初始元素。每次调用 KthLargest.add，返回当前数据流中第K大的元素。
import java.util.PriorityQueue;
public class KthLargest {
private PriorityQueue<Integer> minHeap;
private int kSize;
public KthLargest(int k, int[] nums) {
kSize = k;
minHeap=new PriorityQueue<Integer>(kSize);
for (int i = 0; i< nums.length; i++){
add(nums[i]);
}
}
public int add(int val) {
if (minHeap.size() < kSize){
minHeap.offer(val);
}else if (minHeap.peek() < val){
minHeap.poll();
minHeap.offer(val);
}
return minHeap.peek();
}
}
Java中PriorityQueue通过二叉小顶堆实现，可以用一棵完全二叉树表示。
关于堆操作： https://shmilyaw-hotmail-com.iteye.com/blog/1775868
操作说明：
| 方法名 | 功能描述 |
|---|---|
| add(Ee) | 在队列头部增加一个元素，如果容量已满，则抛出异常，成功则返回true。 |
| clear() | 清空 |
| contains(Objecto) | 检查是否包含当前参数元素 |
| offer(Ee) | 在队列头部增加一个元素，如果容量已满，则返回false，成功加入，返回true。 |
| peek() | 返回队列头部节点，但不移除队列头节点。 |
| poll() | 将队列头部元素移出队列并返回。 |
| remove(Objecto) | 将队列头部元素移出队列并返回，如果队列为空，则抛出异常。 |
| size() | 返回长度 |
如果此文章能给您带来小小的提升，不妨小额赞赏我一下，以鼓励我写出更好的文章！
微信打赏
支付宝打赏
以上就是本文的全部内容，希望本文的内容对大家的学习或者工作能带来一定的帮助，也希望大家多多支持 码农网
本站部分资源来源于网络，本站转载出于传递更多信息之目的，版权归原作者或者来源机构所有，如转载稿涉及版权问题，请联系我们。
