【剑指offer】40.最小的K个数
程序员文章站
2022-07-10 15:41:56
...
题目描述
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。
思路
构建最大堆:
- 堆未满时插入
- 堆已满的时候比较堆顶元素和插入元素大小,插入元素小则替换栈顶元素
- 取出堆元素返回
public static ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
int length = input.length;
if (length < k || k <= 0) return res;
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < length; i++) {
if (maxHeap.size() != k) {
maxHeap.add(input[i]);
} else if (maxHeap.peek() > input[i]) {
maxHeap.poll();
maxHeap.offer(input[i]);
}
}
res.addAll(maxHeap);
return res;
}
public static void main(String[] args) {
int[] arr = {4, 5, 1, 6, 2, 7, 3, 8};
ArrayList<Integer> integers = GetLeastNumbers_Solution(arr, 4);
for (int num : integers) {
System.out.print(num + " ");
}
}
上一篇: Postwoman跨域问题 has been blocked by CORS policy: No ‘Access-Control-Allow-Origin‘ header is present
下一篇: HTTP协议简介
推荐阅读