一道算法题：第K大的数

给一个无序的包涵n个元素的数组，找出其中第k大的数（n > k）。
初看到这个题的时候，作为一个写了一段时间java的人，立刻能想到的一种解法就是：

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

时间复杂度时NlgN, 空间复杂度时O(1).
看起来貌似不错，但既然这道题目被广泛地讨论，就肯定还有其他解法，比如说：

class Solution {
    public int kthLargestElement(int k, int[] nums) {
        // write your code here
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        for(int val : nums) {
            pq.add(val);
            if(pq.size() > k) {
                pq.poll();
            }
        }
        return pq.peek();
    }
};

当然建堆需要额外的空间，而且时间复杂度上并没有多少提升，所以不能算什么优化。
更好的一种解法是利用快速排序的划分思想，这种解法是一种O(n)的解法

class Solution {
    
    public int kthLargestElement(int k, int[] nums) {
        //打乱数组避免最坏情况
        shuffle(nums);
        k = nums.length - k;
        int lo = 0, hi = nums.length - 1;
        while(lo < hi){
            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[] nums, int lo, int hi){
        int i = lo;
        int j = hi + 1;
        while(true){
            while(i < hi && nums[++i] < nums[lo]);
            while(j > lo && nums[lo] < nums[--j]);
            if(j <= i) break;
            exch(nums, i, j);
        }
        exch(nums, lo, j);
        return j;
    }
    
    private void exch(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
  
    private void shuffle(int a[]) {
        Random random = new Random();
        for(int ind = 1; ind < a.length; ind++) {
            int r = random.nextInt(ind + 1);
            exch(a, ind, r);
        }
    }
};