题目
链接：https://leetcode-cn.com/problems/kth-largest-element-in-an-array
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
代码模板
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
}
};
二分查找
解析
可以使用二分查找，查找目标是[left,right]之间第一个大于自身的其他元素个数小于k的数，这个数即为数组排序后的第 k 个最大的元素。
算法的时间复杂度为O(nlogn)，和直接排序、最小堆的耗时差不多。
优点：
代码
class Solution
{
public:
int findKthLargest(vector<int>& nums, int k)
{
auto minmax = minmax_element(nums.begin(), nums.end());
int left = *minmax.first;
int right = *minmax.second;
int mid;
int countGreat;
while (left < right)
{
mid = left + (right - left) / 2;
countGreat = count_if(nums.begin(), nums.end(), [mid](int n) { return n > mid; });
if (countGreat >= k)
{
left = mid + 1;
}
else
{
right = mid;
}
}
return left;
}
};