Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

本题可使用优先队列。

Java中的优先队列底层实际是一个二叉堆。具体可看源码。

public int findKthLargest(int[] nums, int k) {
        Queue<Integer> queue = new PriorityQueue<>(nums.length, (a1, a2) -> {
            return a2 - a1;
        });
        for(int i = 0; i < nums.length; ++i) {
            queue.add(nums[i]);
        }
        for(int i = 0; i < k - 1; ++i) {
            queue.poll();
        }
        return queue.poll();
    }