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.

一刷
Quick select
最好的情况下：
Discard half each time: n+(n/2)+(n/4)..1 = n + (n-1) = O(2n-1) = O(n), because n/2+n/4+n/8+..1=n-1.
原理是每次随机取一个pivot, 然后把大于pivot的都放在右边，小于pivot的都放在左边。如果pivot就在k的位置，直接返回，否则缩小范围继续上面的步骤

public class Solution {
    public int findKthLargest(int[] nums, int k) {
        if(nums == null || nums.length == 0) return Integer.MAX_VALUE;
        //nums.length - k, the start position of last k
        return find(nums, 0, nums.length-1, nums.length - k);
    }
    
    private int find(int[] nums, int start, int end, int k){
        if(start>end) return Integer.MAX_VALUE;
        int pivot = nums[end];
        int left = start;
        for(int i=start; i<end; i++){
            if(nums[i]<=pivot){
                swap(nums, left, i);
                left++;
            }
        }
        swap(nums, left, end);
        if(left == k) return nums[left];//found
        else if(left<k) return find(nums, left+1, end, k);
        else return find(nums, start, left-1, k);
    }
    
    private void swap(int[] nums, int left, int right){
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}