题目链接：https://leetcode.com/problems/kth-largest-element-in-an-array/description/。
解题之前，先回顾下快速排序的过程：
- 从数组中选定基准数，即pivot；
- 搬运元素，将数组中小于pivot的元素放到pivot前面，大于pivot的元素放于pivot后面；
- 对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];
}
}
