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

Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.

Solution

1. 如果能找到K个最大值，那么这K个最大值中smallest element，就是要求的第k个最大值。
2. 用Min-Heap来记录这k个最大值，最后最小值就是答案。

• 过程：扫描input 数组，过程中需保证min-Heap只有k个值 ==>
  -- 若Min-Heap中不满k个值，直接insert current number
  -- 若超过k个值，则需要与min-Heap中最小的值进行比较，会遇到两种情况：
  1. current number < heap min： 不需要， 它不可能成为k个最大值中的一个，不作操作。
  2. current number > heap min: 需要，可能成为k个最大值中的一个。但需保证heap中只有k个值，所以
     1). remove heap min.
     2). offer current number into heap

O (nLogk)

n: number of the input number
k: height of the heap binary tree

class Solution {
    public int findKthLargest(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        //Use min-heap, implemented by PriorityQueue, by default is min-heap
        PriorityQueue <Integer> minHeap = new PriorityQueue<> (k);
        
        for (int num : nums) {
            if (minHeap.size () < k) {
                minHeap.offer (num);
                continue;
            }
            
            if (num > minHeap.peek ()) {
                minHeap.poll ();
                minHeap.offer (num);
            }
        }
        
        return minHeap.peek ();
    }
}