题解 | #最小的K个数#

#include <queue>
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());
        ret.assign(input.begin(), input.begin()+k);
        return ret;

        */
        vector<int> ret;
        if(k==0||k>input.size()){
            return ret;
        }

        priority_queue<int,vector<int>> heapK;
        //iterate the array,if the number of elements in the array is smaller than k,push
        //greater,compare the largest number in k with the current element,choose the smaller
        

        for(const int CurVal:input){
            if(heapK.size()<k){
                heapK.push(CurVal);
            }
            else if(CurVal<heapK.top()){
                heapK.pop();
                heapK.push(CurVal);
            }
        }
        while(!heapK.empty()){
            ret.push_back(heapK.top());
            heapK.pop();
        }

        return ret;


    }
};

·大小为k的堆插入复杂度为 log2 k

·