MinimumK

发表于 更新于 分类于

题目描述[原题链接][https://www.acwing.com/problem/content/description/49/]

输入n个整数，找出其中最小的k个数。

注意：

  • 数据保证k一定小于等于输入数组的长度;
  • 输出数组内元素请按从小到大顺序排序;

样例

1
2
3
输入：[1,2,3,4,5,6,7,8] , k=4

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

算法描述

使用优先队列结构，实现一个大根堆，遍历数组，每次添加一个元素到结果列表中，如果列表长度只大于k，弹出最大的元素，继续遍历，完成遍历之后，将结果集中的元素反转得到结果，返回结果列表

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> getLeastNumbers_Solution(vector<int> input, int k) {
        priority_queue<int> que;
        for(auto t:input){
            que.push(t);
            if(que.size()>k){
                que.pop();
            }
        }
        
        vector<int> ans;
        
        while(que.size()){
            ans.push_back(que.top());
            que.pop();
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public List<Integer> getLeastNumbers_Solution(int [] input, int k) {
        
        Comparator<Integer> cmp = new Comparator<Integer>(){
            public int compare(Integer e1,Integer e2){
                return e2-e1;
            }
        };
        
        PriorityQueue<Integer> que = new PriorityQueue<>(cmp);
        
        for(int t : input){
            que.add(t);
            if(que.size()>k)que.poll();
        }
        
        List<Integer> ans = new ArrayList<>(que);
        
        Collections.sort(ans);
        return ans;
    }
}