NC119 #最小的K个数#

思路一：先排序，后取前k个数。

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> ret;
        if (k==0 || k>input.size()) 
            return ret;
        sort(input.begin(), input.end());
        return vector<int>({input.begin(), input.begin()+k});  
    }
};

思路二：优先队列：

class Solution {
public:
    vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
        int len = input.size();
        vector<int> ans;
        if(k == 0 || k > len)
            return ans;
        priority_queue<int, vector<int> > que;
        for(int val: input)
        {
            if(que.size() < k)
                que.push(val);
            else
            {
                if(que.top() > val)
                {
                    que.pop();
                    que.push(val);
                }
            }
        }
        while(!que.empty())
        {
            ans.push_back(que.top());
            que.pop();
        }
        return ans;
    }
};