剑指 Offer 40. 最小的k个数

输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。

输入：arr = [3,2,1], k = 2
输出：[1,2] 或者 [2,1]

输入：arr = [0,1,2,1], k = 1
输出：[0]

解题思路：

排序取前k个

排序后直接取值，无难度可言，使用这种解法容易被面试官直接给挂知乎上去让人看笑话

最大堆

使用最大堆的性质，先将堆填k个，然后每次进堆都做判断，如果堆顶元素大于当前遍历的数组元素，就将堆顶的移除，将数组元素加入堆中，最后得到的k个就是top k

AC代码：

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> vec(k,0);
        if(k == 0){
            return vec;
        }

        priority_queue<int> que;
        for(int i = 0;i < k;i++){
            que.push(arr[i]);
        }

        for(int i = k;i < arr.size();i++){
            if(que.top() > arr[i]){
                que.pop();
                que.push(arr[i]);
            }
        }

        for(int i = 0;i < k;i++){
            vec[i] = que.top();
            que.pop();
        }

        return vec;
    }
};