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.

无脑解法，上来排序，然后返回第k大的数（这里可以Note里备注的k永远合法）

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size() - k];
    }
};

让人惊讶的是试水解法居然击败80%的提交：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        sort(nums.begin(),nums.end());
        return nums[nums.size() - k];
    }
};

另一种方法是使用stl的heap:

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        make_heap(nums.begin(),nums.end());
        for(int i = 0;i < k - 1;i++)
        {
            pop_heap (nums.begin(),nums.end()); 
            nums.pop_back();
        }
        
        return nums.front();
    }
};

运行结果：

Runtime: 24 ms, faster than 61.26% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10.2 MB, less than 57.31% of C++ online submissions for Kth Largest Element in an Array.

内置函数nth_element：

Rearranges the elements in the range [first,last), in such a way that the element at the nth position is the element that would be in that position in a sorted sequence.

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        //这里使用k-1原因是如果last等于end，算法无效
        nth_element(nums.begin(), nums.begin() + k - 1 , nums.end(), greater<int>());
        return nums[k - 1];
    }
};

执行结果击败100%

Runtime: 4 ms, faster than 100.00% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 10.1 MB, less than 78.18% of C++ online submissions for Kth Largest Element in an Array.

另一个内置函数可以解决这个问题：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        partial_sort(nums.begin(), nums.begin() + k, nums.end(), greater<int>());
        return nums[k - 1];
    }
};