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.

For example,
Given [3,2,1,5,6,4] and k = 2, return 5.

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

Solution1：Sort后輸出nums[k - 1]

思路：升序排序nums后，直接輸出nums[k - 1]。
Time Complexity: O(NlogN) Space Complexity: O(1)

Solution2：最小堆過濾

思路：最小堆過濾，建立min_heap(size：k)來維護(hù)當(dāng)前前k個大的元素，輸出第k個

The default PriorityQueue is implemented with Min-Heap, that is the top element is the minimum one in the heap.
poll() Retrieves and removes the head

C++: std::priority_queue default: max heap,
java/python: priorityqueue: min-heap

Time Complexity: O(k + Nlogk) , k: 建堆
Space Complexity: O(k) (Since可以直接在原序列上做：O(1))

Solution2.5：最小堆過濾 Round1

Time Complexity: O(k + Nlogk) , k: 建堆
Space Complexity: O(k) (Since可以直接在原序列上做：O(1))

Solution3：堆排序，建立max_heap(size：N)來排出k個大的元素，輸出第k個

思路：
Time Complexity: O(N + k * logN) Space Complexity: O(N)

Solution4：類似快排的Partition

思路：因?yàn)槭且业降趉個大的元素，所以每次以一個pivot來重排數(shù)組，使得大于pivot的元素在pivot的左邊，小于pivot的元素在pivot的右邊，
實(shí)現(xiàn)過程類似快速排序(前后雙指針，比較，交換)，
比如原數(shù)組為nums = [*3, 1, 2, 4, 5]，如選中3作為pivot(選pivot的過程有隨機(jī)成分，這也是有可能出現(xiàn)worse case的原因)，一次重排后數(shù)組變?yōu)椋?br> nums = [5, 4, 3, 2, 1]，將pivot=3的位置記為pos，若此時k - 1 < pos，說明第k個大的元素肯定在左邊部分，
所以后續(xù)只需要在左邊部分[5,4]重復(fù)選擇pivot重排的過程；相反同理，若k - 1 > pos，則在右邊部分重排..；若k == pos直接返回。
這樣一來，如果pivot選的數(shù)(隨機(jī)成分)接近median，相當(dāng)于每次二分，則：T(n) = T(n/2) + O(n)，O(n)是重排的過程，可解得T(n) = O(n)。
實(shí)現(xiàn)上：可剛開始在輸入上shuffle一下，保證"更加無序"
所以Average是近似二分，時間復(fù)雜度 Average: O(N), Worst: O(NN)
Space Complexity: O(1)

Solution1 Code：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        Arrays.sort(nums);
        return nums[nums.length - k];
    }
}

Solution2 Code：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        final PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int val : nums) {
            pq.offer(val);

            if(pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
}

Solution2.5 Code：

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

Solution3 Code：

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        // build max-heap
        for(int val : nums) {
            pq.offer(val);
        }
       
       // pop k times
        int result = 0;
        for (int i = 0; i < k; i++) {
            result = pq.poll(); 
        }
        return result;

    }
}

Solution4 Code：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // shuffle(nums);
        k = nums.length - k;
        int lo = 0;
        int hi = nums.length - 1;
        while (lo < hi) {
            final int j = partition(nums, lo, hi);
            if(j < k) {
                lo = j + 1;
            } else if (j > k) {
                hi = j - 1;
            } else {
                break;
            }
        }
        return nums[k];
    }
    
    private int partition(int[] a, int lo, int hi) {
        int i = lo;
        int j = hi + 1;
        while(true) {
            while(i < hi && less(a[++i], a[lo]));
            while(j > lo && less(a[lo], a[--j]));
            if(i >= j) {
                break;
            }
            exch(a, i, j);
        }
        exch(a, lo, j);
        return j;
    }

    private void exch(int[] a, int i, int j) {
        final int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }
    
    private boolean less(int v, int w) {
        return v < w;
    }

    // Reservoir Sampling
    private void shuffle(int a[]) {
        final Random random = new Random();
        for(int ind = 1; ind < a.length; ind++) {
            final int r = random.nextInt(ind + 1);
            exch(a, ind, r);
        }
    }
}