在未排序的数组中找到第 k 个最大的元素。请注意,你需要找的是数组排序后的第 k 个最大的元素,而不是第 k 个不同的元素。
知识点:java的优先队列(PriorityQueue),最小堆
/** PriorityQueue,一个基于优先级堆的*优先级队列。 实际上是一个堆(不指定Comparator时默认为最小堆),可以通过传入自定义的Comparator函数来实现储存不同数据类型的二叉堆。 */ PriorityQueue<Integer> minHeap = new PriorityQueue<>(); // 最小堆,默认容量11 // 最大堆,容量指定为11 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(11, new Comparator<Integer>() { public int compare(Integer i1, Integer i2) { return i2 - i1; } });
/**
对于该题,只需要维持一个最小堆,堆中储存k个元素。每次加入元素时都判断该元素和堆顶元素的大小,如果新元素大于堆顶元素,则将其加入堆中
*/
class Solution {
private PriorityQueue<Integer> minHeap;
public Solution() {
minHeap = new PriorityQueue<>(); // 最小堆
}
public int findKthLargest(int[] nums, int k) {
for (int i = 0; i < nums.length; i++) {
if (minHeap.size() < k) {
minHeap.add(nums[i]);
continue;
}
if (nums[i] > minHeap.peek()) {
minHeap.poll();
minHeap.add(nums[i]);
}
}
return minHeap.peek();
}
}