【LeetCode】【剑指offer】【最小的k个数】

剑指 Offer 40. 最小的k个数

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

示例 1：

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

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

限制：

0 <= k <= arr.length <= 10000
0 <= arr[i] <= 10000

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

  

一、直接排序，返回前k个 

首先我们可以采用将我们的容器中的数据全部都排序然后取出其中最小的k个的方法。 

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        sort(arr.begin(),arr.end());
        vector<int> result;
        while(k--)
        {
            result.push_back(arr[k]);
        }
        return result;
    }
};

二、构建大根堆

class Solution {
public:
    vector<int> getLeastNumbers(vector<int>& arr, int k) {
        vector<int> result;
        //构建大根堆
        //less表示的是如果数据越大，优先级越大
        priority_queue<int,vector<int>,less<int>> heap;
        //保证我们的堆中始终存储的是最小的k个数据。
        //因为大根堆中堆顶的元素始终是最大的元素，所以我们一旦堆的大小大于了k
        //将我们堆顶的元素pop即可。
        for(auto element:arr)
        {
            heap.push(element);
            if(heap.size()>k)
            {
 
                cout<top()<
                heap.pop();
            }
        }
        //将我们堆中的元素依次放入一个容器中，作为我们的返回结果。
        while(!heap.empty())
        {
            result.push_back(heap.top());
            heap.pop();
        }
        return result;
    }
};