215. Kth Largest Element in an A

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.

class Solution {
public:
        int findKthLargest(vector<int>& nums, int k) {
        return sort(nums, 0, nums.size()-1, k);
    }

        int sort(vector<int>& nums, int low, int hight, int k) {
        int flag = nums[hight];
        int left = low;
        int right = hight;
        while(low < hight){
            while(nums[low] >= flag && low < hight) low++;
            nums[hight] = nums[low];
            while(nums[hight] <= flag && low < hight) hight--;
            nums[low] = nums[hight];
        }
        nums[low] = flag;
        if(low == k-1) return flag;
        else if(low < k-1) return sort(nums, low+1, right, k);
        else return sort(nums, left, low-1, k);
    }
};

Runtime: 28 ms, faster than 35.55% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.8 MB, less than 21.26% of C++ online submissions for Kth Largest Element in an Array.

思路

• 快排（从大到小，选择最后一个元素作为枢纽）
• 每一次迭代后比较枢纽的索引与k的大小
• index == k return nums[index]; index > k return sort(left area); index < k return sort(right area)

优化

• heap？
• etc.