Kth Largest Element II

Find K-th largest element in an array. and N is much larger than k.

https://aaronice.gitbooks.io/lintcode/content/data_structure/kth_largest_element.html
我的思路基本上跟这个里面写的一致
There are 3 ways to solve this question.
1st - Sort the whole list and find the kth number. Time O(nlongn) Space O(1) if using quick sort
2nd - Maintain a min heap with size of k. If the number is larger than the smallest value in the heap, update the heap. In the end the kth number is the top of the heap. Time O(nlongk) Space O(k)
3nd - Maintain a max heap with size of k. Always update the heap while iterating through the number array. Once the size of the heap is larger than k, pop the smallest number out. However in the end, the top of the heap is the largest number. So we should pop k - 1 numbers out of the heap and get the last number as our result. Time O(nlogk) Space O(k)
4th - Quick Select. Choose a pivot number and do partition. If we choose the middle number as our pivot our choose a pivot randomly, the time complexity is between O(n) and O(n^2). The Space complexity is O(1), better than using a heap.

In this follow up question, since we are told that N is much larger than k, we know that O(nlogk) is approximately equal to O(n). So using a heap is a better choice.
class Solution {
    /**
     * @param nums an integer unsorted array
     * @param k an integer from 1 to n
     * @return the kth largest element
     */
    public int kthLargestElement2(int[] nums, int k) {
        // Write your code here
        if (nums == null || nums.length == 0) return -1;
        PriorityQueue<Integer> pq = new PriorityQueue<>(k);
        for (int i = 0; i < nums.length; i++) {
            if (pq.size() < k) {
                pq.offer(nums[i]);
            } else {
                if (nums[i] > pq.peek()) {
                    pq.poll();
                    pq.offer(nums[i]);
                }
            }
        }
        return pq.peek();
    }
};