*LeetCode-Kth Largest Element in an Array

三種方法 1 排序 2 min heap 3 max heap

我用了3 其實2更直覺 隻是要想清楚 

因為heap是用priority queue實作的 每次隻能得到queue head 是以要是min 就要使用k個 記錄的是最大的k個

 要是max就要使用 n - k + 1個 記錄的是最小的幾個

再有就是comparator的實作 注意傳回值的意義 隻要是升序的 那麼就傳回 int1 - int2

降序就是 int2 - int1

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<Integer> maxHeap = new PriorityQueue ( n - k + 1, new Comparator<Integer>(){
                public int compare ( Integer i, Integer j ){
                    return j - i;
                }
            });
        for ( int i = 0; i < n - k + 1; i ++ )
            maxHeap.offer(nums[i]);
        for ( int i = n - k + 1; i < n; i ++ ){
            if ( nums[i] < maxHeap.peek() ){
                maxHeap.poll();
                maxHeap.offer( nums[i] );
            }
        }
        return maxHeap.peek();
    }
}