最大堆迭代，海量数据时十分实用

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;
    }
};