小根堆
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>,greater<int>> q;
for(auto x:nums)
{
if(q.size()<k)
q.push(x);
else if(q.top()<x)
{
q.pop();
q.push(x);
}
}
return q.top();
}
};
大根堆
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>> q;
for(auto x:nums)
q.push(x);
int t=k-1;
while(t--)
q.pop();
return q.top();
}
};
快速排序
class Solution {
public:
int quick(vector<int>& q, int k,int l,int r)
{
if(l==r) return q[r];
int x=q[(l+r)>>1];
int i=l-1,j=r+1;
while(i<j)
{
do i++;while(q[i]<x);
do j--;while(q[j]>x);
if(i<j) swap(q[i],q[j]);
}
int cnt=j-l+1;
if(k<=cnt)//答案在左边
return quick(q,k,l,j);
else return quick(q,k-cnt,j+1,r);
}
int findKthLargest(vector<int>& nums, int k) {
return quick(nums,nums.size()-k+1,0,nums.size()-1);
}
};