題目鏈接：https://leetcode.com/problems/kth-largest-element-in-an-array/description/。
解題之前锨苏，先回顧下快速排序的過程：
- 從數(shù)組中選定基準(zhǔn)數(shù)耿币，即pivot梳杏；
- 搬運(yùn)元素，將數(shù)組中小于pivot的元素放到pivot前面淹接，大于pivot的元素放于pivot后面十性；
- 對pivot前面和后面的兩個子序列遞歸上述操作，直至子序列的長度為1或?yàn)榭铡?/li>
快排原理不算深奧塑悼，但第二步元素搬運(yùn)容易亂或者說思路不明朗劲适，這里推薦一篇博客：白話經(jīng)典算法系列之六 快速排序 快速搞定，這個博主表達(dá)了一種挖坑填數(shù)的方法厢蒜，有利于理解和記憶霞势。具體代碼可以看博客。
回歸正題斑鸦，這道題是快排的延伸愕贡，面試容易遇到。理解了快排思想巷屿，也容易想到這道題的思路固以。快排時，每一次將序列分成子序列時憨琳，pivot的index或者比k大诫钓，或者比k小，不斷通過index去逼近k篙螟，得到答案菌湃。
Accept代碼如下：
class Solution {
public int findKthLargest(int[] nums, int k) {
// 數(shù)組的第k大即第n-k小，轉(zhuǎn)換一下
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;
// 這里采用的是那篇博主的挖坑填數(shù)法遍略，邏輯很清晰
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];
}
}
