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大个数 -->（ 有序情况下 ， index =k-1 的值）
这里我采用 快选的方法
时间复杂度 O(n) 空间复杂度O(1)
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 第K大 index 为 k-1
quickselect(nums,0,nums.size()-1,k-1);
return nums[k-1];
}
private:
void quickselect(vector<int>& nums, int l, int r,int k){
// 快排 l..j > nums[l]
// i..r < nums[l]
int j = l;
for(int i = l+1; i <= r; i++ ){
if(nums[i] > nums[l]){
j++;
swap(nums[i],nums[j]);
}
}
swap(nums[l],nums[j]);
// nums[l..j] >= nums[l] >= nums[i..r]
//快选
if(j >k) quickselect(nums,l,j,k);
else if (j <k) quickselect(nums,j+1,r,k);
//招到某次 j == k
else return;
}
};
image.png
当然 也可以用堆排序 需要额外开O(k)的空间 时间复杂度O(NlogK)
c++ 中 priority_queue 默认是 最大堆
image.png
#include <queue>
using namespace std;
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
// 求第K大个元素 --> 一个 大小为K的 小顶堆的 堆顶
priority_queue<int, vector<int>, greater<int> > minp;
//把数组所有元素都往 最小堆里塞 同时维护 最小堆大小为K
for(auto i:nums){
minp.push(i);
if(minp.size() > k){
minp.pop();
}
}
return minp.top();
}
};
image.png
