求数据流中的第K大元素
题目
设计一个找到数据流中第K大元素的类(class)。注意是排序后的第K大元素,不是第K个不同的元素。
你的 KthLargest 类需要一个同时接收整数 k 和整数数组nums 的构造器,它包含数据流中的初始元素。每次调用 KthLargest.add,返回当前数据流中第K大的元素。
示例:
说明:
你可以假设 nums 的长度≥ k-1 且k ≥ 1。
解法
我们可以使用 Java内部提供的优先级队列PriorityQueue,PriorityQueue是一个内部能够自动排序的队列,往PriorityQueue添加一个元素后,它能自动给整个序列重新排序,确保整个序列从队头到队尾按从小到大排列。
PriorityQueue的底层实现是一个小顶堆。
另外,题目要求找到数据流中第K大元素,我们可以限定PriorityQueue最大容量为K,这样PriorityQueue按从小到大排列之后,首元素就是我们要的元素,也就是第K大元素。
代码实现:
class KthLargest {
final PriorityQueue<Integer> queue;
final int k;
public KthLargest(int k, int[] nums) {
this.k = k;
queue = new PriorityQueue<Integer>(k);
for (int i: nums) {
add(i);
}
}
public int add(int val) {
if(queue.size() < k) {
queue.offer(val);
} else if(queue.peek() < val) {
queue.poll();
queue.offer(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);
*/