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] 即可。
- 但是在快速排序中，我们将数组分为左半部分和右半部分。由于只需要寻找第 k 大，当 k 小于左半部分元素时，第 k 大一定在左半，否则一定在右半，这样只需对其中一半排序即可。
- 画出递归树可以发现，完整的快速排序是一整棵递归树，而优化后成为了一条路径，时间复杂度大幅度缩小。
- 细节上由于快排实现上左边划分（l, j）和右边划分（i, r）可能存在 （j, i） 或者 （j, 某个元素，i），所以 k 可能在左边部分中，右边部分中或者直接是“某个元素”，所以划分情况往下递归时要注意区分三种情况。
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); // 递归右边
// 否则就是 “某个元素”，直接终止递归即可
}
};
