最大堆迭代，海量数据时十分实用
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int>ans;
if(input.size()<k||k<=0)return ans;
priority_queue<int,vector<int>,less<int>>p;
for(int i=0;i<input.size();i++)
{
if(p.size()<k)p.push(input[i]);
else if(p.top()>input[i])
{
p.pop();
p.push(input[i]);
}
}
while(!p.empty())ans.push_back(p.top()),p.pop();
return ans;
}
};
找第k-1大的数
class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int>ans;
if(input.size()==0||k<=0||k>input.size())return ans;
int L=0,R=input.size()-1;
int index=partition(input,L,R);
while(index!=k-1)
{
if(index<k-1)L=index+1;
else R=index-1;
index=partition(input,L,R);
}
for(int i=0;i<k;i++)ans.push_back(input[i]);
return ans;
}
int partition(vector<int>&a,int L,int R)
{
int i=L,j=R,p=a[L];
while(i<j)
{
while(i<j&&a[j]>=p)j--;
a[i]=a[j];
while(i<j&&a[i]<=p)i++;
a[j]=a[i];
}
a[i]=p;
return i;
}
};
