[2018-09-16] [LeetCode-Week2] 21

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.

1. 我们可以用快速排序，排好序后直接输出 nums[k-1] 即可。
2. 但是在快速排序中，我们将数组分为左半部分和右半部分。由于只需要寻找第 k 大，当 k 小于左半部分元素时，第 k 大一定在左半，否则一定在右半，这样只需对其中一半排序即可。
3. 画出递归树可以发现，完整的快速排序是一整棵递归树，而优化后成为了一条路径，时间复杂度大幅度缩小。
4. 细节上由于快排实现上左边划分（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);  //   递归右边
        //   否则就是 “某个元素”，直接终止递归即可
    }
};