LeetCode215-数组中的第K个最大元素

LeetCode215-数组中的第K个最大元素

优先队列/堆实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
PriorityQueue<Integer> queue = new PriorityQueue<>(k,Comparator.comparingInt(a -> a));
for (int i = 0; i <len ; i++) {
// Java 里没有 heapify ,因此我们逐个将前 k 个元素添加到 heap 里
if (queue.size()<k){
//前k个数添加到小顶堆
queue.offer(nums[i]);
}else {
// 只要当前遍历的元素比堆顶元素大,堆顶弹出,遍历的元素进去
if (nums[i]>queue.peek()){
// Java 没有 replace(),所以得先 poll() 出来,然后再放回去
queue.poll();
queue.offer(nums[i]);
}
}
}
return queue.peek();
}