Medium

這題很明顯，并非那么簡(jiǎn)單. 邏輯很直白的，多半是想考你最優(yōu)解法，時(shí)間空間復(fù)雜度最低。

我用的最intuitive的解法，建立一個(gè)從大到小的priorityQueue, 把所有數(shù)組元素丟進(jìn)去，然后一個(gè)一個(gè)取取到第k個(gè).
O(N lg K) running time + O(K) memory
為什么這里時(shí)間復(fù)雜度是O(NlgK)而不是O(N)呢，因?yàn)閜riorityQueue本質(zhì)上是Binary heap, which is quite like a complete binary tree. 它的insert()和delete()都是O(lgK)，而我們遍歷了array里的N個(gè)元素來進(jìn)行insert or delete, 所以是O(Nlg

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>(nums.length, new Comparator<Integer>(){
            public int compare(Integer a, Integer b){
                return b - a;
            }
        });
        for (Integer i : nums){
            pq.offer(i);
        }
        int topK = 0;
        while (k > 0){
            topK = pq.poll();
            k--;
        }
        return topK;
    }
}

然而這肯定不是面試官想要的解法，為了這個(gè)寫這個(gè)QuickSelect解法我花了感覺大半天時(shí)間吧。