题目描述

blablabla

样例

blablabla

算法1(堆)

利用大根堆维护前k个最小的数，从k+1遍历后面的元素，如果当前元素小于队首元素，删除队首元素，将当前元素放入

class Solution {
public:
    priority_queue<int> q;
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        vector<int> res(k,0);
        if (input.size()==0) return res;
        for (int i=0;i<k;i++) q.push(input[i]);
        for (int i=k;i<input.size();i++) {
            if (q.top()>input[i]) {
                q.pop();
                q.push(input[i]);
            }
        }
        for (int i=k-1;i>=0;i--) {
            res[i]=q.top();
            q.pop();
        } 
        return res;
    }
};