LeetCode 215 数组中第K个最大元素

在未排序的数组中找到第 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();

    }
}
上一篇:leetcode-寻找两个正序数组的中位数


下一篇:数据结构——最小堆