题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素。
示例：
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
解题思路
方法1：使用快排，每次返回当前正确归位元素的下标，直至下标与'k'一致。
int partition(vector<int>& nums, int start, int end){
int small = start - 1;
for(int idx=start; idx<end; idx++){
if(nums[idx]<nums[end]){
small++;
swap(nums[small], nums[idx]);
}
}
small++;
swap(nums[small], nums[end]);
return small;
}
int findKthLargest(vector<int>& nums, int k) {
k = nums.size() - k;
int start = 0, end = nums.size() - 1;
int index = partition(nums, start, end);
while(index!=k){
if(index>k)
end = index - 1;
else
start = index + 1;
index = partition(nums, start, end);
}
return nums[index];
}
时间复杂度为O(n)，空间复杂度O(1)
同样，快排方法也可以用于无序数组查找最大、最小值，相比于遍历整个数组要稍微优化一些。
方法2：维护一个大小为k的小顶堆，不断将数组元素喂进去，直至结束。最后返回堆顶。
int findKthLargest(vector<int>& nums, int k) {
//升序的优先队列
priority_queue <int,vector<int>,greater<int> > ascending;
for (int &i:nums)
{
ascending.push(i);
if (ascending.size()>k)
ascending.pop();
}
return ascending.top();
}
时间复杂度为O(nlog(k))，空间复杂度为O(k)。
