求解数组第k大元素（快排思想）

题目链接：https://leetcode.com/problems/kth-largest-element-in-an-array/description/。
解题之前，先回顾下快速排序的过程：

1. 从数组中选定基准数，即pivot；
2. 搬运元素，将数组中小于pivot的元素放到pivot前面，大于pivot的元素放于pivot后面；
3. 对pivot前面和后面的两个子序列递归上述操作，直至子序列的长度为1或为空。

快排原理不算深奥，但第二步元素搬运容易乱或者说思路不明朗，这里推荐一篇博客：白话经典算法系列之六 快速排序 快速搞定，这个博主表达了一种挖坑填数的方法，有利于理解和记忆。具体代码可以看博客。
回归正题，这道题是快排的延伸，面试容易遇到。理解了快排思想，也容易想到这道题的思路。快排时，每一次将序列分成子序列时，pivot的index或者比k大，或者比k小，不断通过index去逼近k，得到答案。
Accept代码如下：

class Solution {
    public int findKthLargest(int[] nums, int k) {
        // 数组的第k大即第n-k小，转换一下
        return helper(nums, 0, nums.length-1, nums.length-k);
    }
    
    public int helper(int[] nums, int lo, int hi, int k)
    {
        int pivot = nums[lo];
        int i = lo, j = hi;
        // 这里采用的是那篇博主的挖坑填数法，逻辑很清晰
        while(i < j)
        {
            while(i < j && nums[j] >= pivot)
            {
                j--;
            }
            if (i<j)
            {
                nums[i] = nums[j];
                i++;
            }
            while(i<j && nums[i] < pivot)
            {
                i++;
            }
            if(i<j)
            {
                nums[j] = nums[i];
                j--;
            }
        }
        nums[i] = pivot;
        // 利用i逼近k
        // k比i大的情形，k在i后面的子序列
        if (i < k)
            return helper(nums, i+1, hi, k);
        // k比i小的情形，k在i前面的子序列
        if (i > k)
            return helper(nums, lo, i-1, k);
        return nums[i];
    }
    
}