题解 | #最小的K个数#

最小的k个数：最直观的想法是，使用sort排序，然后遍历数组返回前k个数或者直接使用迭代器返回前k个数。

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.size()==0)
            return res;
        sort(input.begin(),input.end());
        //不能越界且为k个数
        for(int i=0;i<k&&i<input.size();i++)
            res.push_back(input[i]);
        return res;
    }

    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res;
        if(input.size()==0)
            return res;
        sort(input.begin(),input.end());
        return vector<int>(input.begin(),input.begin()+k);
    }

优化：使用STL中的优先级队列priority_queue来实现大根堆。维护一个大小为k的大根堆，遍历数组，如果大根堆的长度小于k则入堆，反之则判断当前元素是否比大根堆堆顶小，如果是则将堆顶元素出堆并且将当前元素入堆，最后剩余的k个元素的大根堆即为所求。同时完成大根堆后可以使用input存储。

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
{
    vector<int> res;
    //数组为空或者k为空或者k大于数组长度则为空
    if(input.size()==0||k==0||k>input.size())
        return res;
    priority_queue<int> pri_que; //优先级队列 大根堆
    for(auto val:input)
    {
        if(pri_que.size()<k)
            pri_que.push(val);
        //维护一个大小为k的大根堆
        else
        {
            //pri_que.top()表示大根堆的最大值
            if(val<pri_que.top())
            {
                //pri_que.pop()弹出的是大根堆的最大值
                pri_que.pop(); 
                pri_que.push(val); //将当前这个较小的压入队列
            }
        }
     }
     while(!pri_que.empty())
     {
         res.push_back(pri_que.top());
         pri_que.pop();
     }
     return res;
}

vector<int> GetLeastNumbers_Solution(vector<int> input, int k) 
{
    vector<int> res;
    //数组为空或者k为空或者k大于数组长度则为空
    if(input.size()==0||k==0||k>input.size())
        return res;
    priority_queue<int> pri_que; //优先级队列 大根堆
    for(auto val:input)
    {
       if(pri_que.size()<k)
          pri_que.push(val);
       //维护一个大小为k的大根堆
       else
       {
           //pri_que.top()表示大根堆的最大值
           if(val<pri_que.top())
           {
               //pri_que.pop()弹出的是大根堆的最大值
               pri_que.pop(); 
               pri_que.push(val); //将当前这个较小的压入队列
           }
        }
     }
     //清空元素
     input.clear();
     while(!pri_que.empty())
     {
        input.push_back(pri_que.top());
        pri_que.pop();
     }
     return input;
}