题解 | #最小的K个数#

1.直接用cmath里面sort()排序
直接排序输入数组，
返回最小的k个

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        sort(input.begin(),input.end());
        vector<int> res;
        if(k>input.size()) return res;
        for(int i=0;i<k;++i) res.push_back(input[i]);
        return res;
    }
};

2.用优先级队列实现堆排序
优先级队列首先是个队列，这里有点public继承的味道，is-a的关系
所以，队列特有“先进先出”
优先级显然大的在前
这边用常值int变量 val来遍历输入数组input， const int val:input，
让人想到python遍历的样子。
首先少于k，就直接入队
大等于k，审核入队，只有比队首最大的小，这是个大顶堆，可以来输出最小的几个值，
举一反三，如果是最大的几个值，应该是用小顶堆，如果有比最小值大的，val>pq.top()，则入队
输出采用了同类型的ret来存放

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if(k==0 || k>input.size()) return ret;
        priority_queue<int,vector<int>>pq;//自动从大到小排序的队列
        for(const int val:input) {//让val遍历input
            if(pq.size()<k){
                pq.push(val);
            }else{
                if(val<pq.top()){
                    pq.pop();
                    pq.push(val);
                }
            }
        }
        while(!pq.empty()){
            ret.push_back(pq.top());
            pq.pop();
        }
        return ret;
    }
};