思路1：小顶堆
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int,vector<int>, greater<int>> q;
for(int i=0;i<nums.size();i++)
{
if(q.size()<k)
{
q.push(nums[i]);
}
else
{
if(nums[i]>q.top())
{
q.pop();
q.push(nums[i]);
}
}
}
return q.top();
}
};
思路2：快速选择
快排的基础上改进
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int N=nums.size();
int target=k-1; //第k大就是N-k小
int l=0,r=N-1;
while(l<=r)
{
int mid=partition(nums,l,r);
if(mid==target)
return nums[mid];
else if(mid<target)
l=mid+1;
else
r=mid-1;
}
return -1;
}
int partition(vector<int>& nums, int left, int right)
{
int pivot=nums[left];
while(left<right)
{
while(nums[right]<pivot && left<right){ right--;}
nums[left]=nums[right];
while(nums[left]>=pivot && left<right){left++;}
nums[right]=nums[left];
}
//cout<<left<<endl;
nums[left]=pivot;
return left;
}
};
