题解 | #最小的K个数#

//使用了堆排序的思路。不是构建一个最小堆，把所有数据排完序后取前K个，而是构建一个最大堆，只保存k个数，这个最小堆我们视它为当前暂时筛选出来的k个最小数。如果有哪个数比这k个最小数中的最大的那个小，就相当于拥有了进入这个最小堆的权力。堆中的最大的这个数我们可以看成是“门槛”。它进来后可以把原本的门槛取而代之。
//如果要求你写的是“最大的K个数”，也没多少要改的，只需要把priority_queue中的第三个模板参数设置为greater（默认用的是less构建大根堆），以构建最小堆来保存最大的k个数。
//找最大的k个数用最小堆，找最小的k个数用最大堆，看起来很矛盾，但实际上这是因为我们并不是对整个数组进行排序，而只是为了在迭代过程中，找到临时筛选出的“topK”里的那个“门槛”，用这个门槛和数组中其他元素进行比较，来迭代整个“topK”的小集合而已。
#include <functional>
#include <queue>
#include <vector>
class Solution {
  public:
    vector<int> GetLeastNumbers_Solution(vector<int>& input, int k)
    {
        //return GetBiggestNumbers_Solution(input, k);
        return GetSmallestNumbers_Solution(input, k);
    }

    vector<int> GetSmallestNumbers_Solution(vector<int>& input, int k) {
        priority_queue<int>q;
        stack<int>temp;
        vector <int>result;
        if (input.size() < k || k <= 0)return result;
        for (int i = 0; i < k; i++) {
            q.push(input[i]);
        }
        for (int i = k; i < input.size(); i++) {
            if (input[i] <
                    q.top()) { //如果当前这个数，比我们目前筛选出来的k个最小值中的最大的那个更小，就说明它可以取而代之。
                q.pop();
                q.push(input[i]);
            }
        }
        while (!q.empty()) {
            temp.push(q.top());
            q.pop();
        }
        while (!temp.empty()) {
            result.push_back(temp.top());
            temp.pop();
        }
        return result;
    }
    vector<int> GetBiggestNumbers_Solution(vector<int>& input, int k) {
        priority_queue<int, vector<int>, greater<> >q;//构建一个最小堆
        stack<int>temp;
        vector <int>result;
        if (input.size() < k || k <= 0)return result;
        for (int i = 0; i < k; i++) {
            q.push(input[i]);
        }
        for (int i = k; i < input.size(); i++) {
            if (input[i] >
                    q.top()) { //如果当前这个数，比我们目前筛选出来的k个最大值中的最小的那个更大，就说明它可以取而代之。
                q.pop();
                q.push(input[i]);
            }
        }
        while (!q.empty()) {
            temp.push(q.top());
            q.pop();
        }
        while (!temp.empty()) {
            result.push_back(temp.top());
            temp.pop();
        }
        return result;
    }
};