剑指offer:最小的K个数
程序员文章站
2022-03-01 12:54:26
...
试题:
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
代码:
使用有序结构存储这k个数就可以了
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList res = new ArrayList<Integer>();
int len = input.length;
if(len==0 || k>len || k==0) return res;
PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>(){
public int compare(Integer o1, Integer o2){
return o2.compareTo(o1);
}
});
for(int num : input){
if(maxHeap.size()!=k){
maxHeap.offer(num);
}else if(maxHeap.peek() > num){
maxHeap.poll();
maxHeap.offer(num);
}
}
for(Integer num: maxHeap) res.add(num);
return res;
}
}
上一篇: elasticsearch 中关键属性、字段等说明
下一篇: 最小的K个数 剑指offer
推荐阅读
-
剑指offer11:输入一个整数,输出该数二进制表示中1的个数。其中负数用补码表示。(进制转换,补码反码)
-
【剑指 Offer 53 - II】0~n-1中缺失的数字
-
剑指offer书(53)-2:0-n-1中缺失的数字
-
剑指OFFER----53-2、0~n-1中缺失的数字(js实现)
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指offer 53 - II. 0~n-1中缺失的数字
-
剑指 Offer 53 - II. 0~n-1中缺失的数字
-
剑指Offer编程题--数组中重复的数字
-
剑指offer—数组(1):数组中重复的数字
-
20190912——剑指offer 面试题3 题目1找出数组中重复的数字