题解 | 最小的K个数

#include <vector>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param input int整型vector 
     * @param k int整型 
     * @return int整型vector
     */
    
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k) {
        vector<int> res;
        if(k==0||k>input.size())
        {
            return res;
        }
        priority_queue<int> pq;
        //采用遍历+最大堆的方式，默认前4个为堆里的成员，此时pq的top为当前4个数的最大值
        //假如数组往后移动一次，进来一个比当前4个数中最大数还要小的数，此时往前看
        //pq中的四个数，一定是这五个数中最小的四个数，同理，再往后移动一个，还是遇到比最大数
        //还要大的数就不push，比最大数要小的数再进来，所以此时pq中的四个数依旧是这六个数中
        //最小的四个数，以此类推，直到数组遍历完成
        //因为往后是遍历一个数并且pop是删一个数，所以这保证了我们只比较pq的top即可，因为只需要把
        //最大值这一个数替换掉，这4个数就是迄今为止见过的最小的4个数
        for(auto i:input)
        {
            if(pq.size()<k)
            {
                pq.push(i);
            }
            else 
            {
              if(i<pq.top())
              {
                 pq.pop();
                 pq.push(i);
              }
            }
        }
        while(!pq.empty())
        {
            res.push_back(pq.top());
            pq.pop();
        }
        return res;
        
    }
};