题目

1
2
3
4
5
6
7
8
9
10
11
输入 n 个整数，找出其中最小的 k 个数。

注意：

输出数组内元素请按从小到大顺序排序;
数据范围
1≤k≤n≤1000
样例
输入：[1,2,3,4,5,6,7,8] , k=4

输出：[1,2,3,4]

题解

点击查看
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
//小根堆
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int, vector<int>, greater<int>> heap;
        vector<int> res;
        
        for(auto c : input){
            heap.push(c);
        }
        
        for(int i = 0; i < k;++i){
            res.push_back(heap.top());
            heap.pop();
        }
        
        return res;
    }
};
//大根堆
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> heap;
        vector<int> res;
        
        for(auto x : input){
            heap.push(x);
            if(heap.size() > k) heap.pop();//如果堆中元素的数量大于k，那就弹出其中最大的数，这样就可以保证堆中始终是最小的k个数
        }
        
        while(heap.size()){
            res.push_back(heap.top());
            heap.pop();
        }
        
        reverse(res.begin(), res.end());
        
        return res;
    }
};