知一的指纹

703. 数据流中的第K大元素

版权声明: 本文为博主原创文章,发表自 知一的指纹。转载需向 我的邮箱 申请。

设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。

你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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()返回长度

如果此文章能给您带来小小的提升,不妨小额赞赏我一下,以鼓励我写出更好的文章!
Noogel's WeChat Pay

微信打赏

Noogel's Alipay

支付宝打赏