找出无序数组中第 K 大的数字。注意是排序后数组的第 K 大数字。

例一：
输入： [3,2,1,5,6,4] and k = 2
输出： 5

例二：
输入： [3,2,3,1,2,4,5,5,6] and k = 4
输出： 4

简单粗暴但并不是最快解，使用小顶堆，直到堆中只剩下 K 个元素，此时最小元素即为第 K 大的元素。

/*
 * 215. Kth Largest Element in an Array
 * https://leetcode.com/problems/kth-largest-element-in-an-array/
 * https://www.whosneo.com/215-kth-largest-element-in-an-array/
 */

import java.util.Comparator;
import java.util.PriorityQueue;

public class FindKthLargest {
    public static void main(String[] args) {
        FindKthLargest solution = new FindKthLargest();

        int[] nums;
        nums = new int[]{3, 2, 1, 5, 6, 4};
        System.out.println(solution.findKthLargest(nums, 2));
        nums = new int[]{3, 2, 3, 1, 2, 4, 5, 5, 6};
        System.out.println(solution.findKthLargest(nums, 4));
    }

    private int findKthLargest(int[] nums, int k) {
        // init heap 'the smallest element first'
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(n -> n));

        // keep k largest elements in the heap
        for (int n : nums) {
            heap.add(n);
            if (heap.size() > k)
                heap.poll();
        }

        // output
        return heap.poll();
    }
}