题目描述
思路:小顶堆
- 维护一个大小为K的小顶堆
- 遍历所有元素:
- 如果当前堆中元素个数小于K,则将元素添加到堆中
- 如果当前堆中元素个数等于K,则判断第K + 1
方法一:
class Solution {
public int findKthLargest(int[] nums, int k) {
// 优先队列
PriorityQueue<Integer> heap = new PriorityQueue<>(
(e1, e2) -> e1 - e2
);
for (int n : nums) {
if (heap.size() < k) {
heap.offer(n);
} else if (heap.size() == k) {
if (heap.peek() < n) {
heap.poll();
heap.offer(n);
}
}
}
return heap.peek();
}
}