https://leetcode.com/problems/kth-largest-element-in-an-array/description/
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.
Example 1:
Input: [3,2,1,5,6,4] and k = 2
Output: 5
Example 2:
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
- 我們可以用快速排序，排好序后直接輸出 nums[k-1] 即可躯砰。
- 但是在快速排序中痪蝇，我們將數(shù)組分為左半部分和右半部分栏赴。由于只需要尋找第 k 大菱属，當(dāng) k 小于左半部分元素時，第 k 大一定在左半单山，否則一定在右半逸爵，這樣只需對其中一半排序即可。
- 畫出遞歸樹可以發(fā)現(xiàn)士嚎，完整的快速排序是一整棵遞歸樹呜魄，而優(yōu)化后成為了一條路徑，時間復(fù)雜度大幅度縮小莱衩。
- 細(xì)節(jié)上由于快排實現(xiàn)上左邊劃分（l, j）和右邊劃分（i, r）可能存在 （j, i） 或者 （j, 某個元素爵嗅，i），所以 k 可能在左邊部分中笨蚁，右邊部分中或者直接是“某個元素”睹晒，所以劃分情況往下遞歸時要注意區(qū)分三種情況。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
divideSort(nums, 0, nums.size()-1, k-1);
return nums[k-1];
}
void divideSort(vector<int>& nums, int l, int r, int k) {
if (l >= r) return;
int s = nums[l];
int i = l, j = r;
while (i <= j) {
while (nums[i] > s) i++;
while (nums[j] < s) j--;
if (i <= j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
i++;
j--;
}
}
if (j >= k) divideSort(nums, l, j, k); // 遞歸左邊
if (i <= k) divideSort(nums, i, r, k); // 遞歸右邊
// 否則就是 “某個元素”括细，直接終止遞歸即可
}
};
