最小K个数
最小 个数
2023-09-27 14:28:31 时间
目录
最小K个数
设计一个算法,找出数组中最小的k个数。以任意顺序返回这k个数均可。
方法一
对原数组从小到大排序后取出前 k 个数
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] vec = new int[k];
Arrays.sort(arr);
for (int i = 0; i < k; ++i) {
vec[i] = arr[i];
}
return vec;
}
}
方法二
用一个大根堆实时维护数组的前 k小值。首先将前 k 个数插入大根堆中,随后从第 k+1 个数开始遍历,如果当前遍历到的数比大根堆的堆顶的数要小,就把堆顶的数弹出,再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可
具体步骤
1. 先使用arr中前k个元素创建大堆
2. 然后使用arr中剩余元素依次与堆顶元素比较,如果小于堆顶元素,替换堆顶元素,即:删除堆顶,然后将arr[i]插入堆中
3. 最后堆中的k个元素就是所需的前k个最小的元素,放到数组中返回
class InitCmp implements Comparator<Integer>{
public int compare(Integer num1,Integer num2){
return num2-num1;
}
}
class Solution{
public int[] smallestK(int[] arr, int k){
if(k == 0){
return new int[0];
}
int[] ret = new int[k];
InitCmp initCmp = new InitCmp();
PriorityQueue<Integer> p = new PriorityQueue<Integer>(k,initCmp);
for (int i = 0; i < k; i++) {
// 先使arr中前k个元素创建大堆
p.offer(arr[i]);
}
for (int i = k; i < arr.length; i++) {
if(arr[i] < p.peek()){
p.poll();
p.offer(arr[i]);
}
}
for (int i = 0; i < k; i++) {
ret[i] = p.poll();
}
return ret;
}
}
时间复杂度:O(nlogk),其中 n是数组 arr 的长度。由于大根堆实时维护前 k小值,所以插入删除都是 O(logk)的时间复杂度,最坏情况下数组里 n个数都会插入,所以一共需要 O(nlogk)
空间复杂度:O(k),因为大根堆里最多 k个数
相关文章
- POJ 1201 差分约束(集合最小元素个数)
- POJ 1716 区间最小点个数
- POJ 1716 区间最小点个数
- HDU 4786(最小生成树 kruskal)
- 【华为OD机试真题 python】 最大N个数与最小N个数的和【2022 Q4 | 100分】
- [MCM] 2017研究生数学建模竞赛A题 3架飞机 TSP 求总路径最小
- 最小的k个数
- 【BZOJ3158】千钧一发 最小割
- ACM入门之【最小生成树】
- 最大公约数与最小公倍数
- 《模式识别》学习笔记(十七)含拒绝判断的最小损失准则,最小最大损失准则
- 【Matlab算法】L-M法求解非线性最小二乘优化问题(附L-M法MATLAB代码)
- 数组输出最小的k个数
- (第11列)C语言练习:输入数组,最大的与第一个元素交换,最小的与最后一个元素交换,输出数组。五步带你解决。
- 4213. 最小结果
- 华为OD机试 - 最小叶子节点(Python) | 机试题+算法思路+考点+代码解析 【2023】
- 华为OD机试 - 最小传递延迟(Java) | 机试题+算法思路+考点+代码解析 【2023】
- [LeetCode] 1000. Minimum Cost to Merge Stones 混合石子的最小花费
- 【bzoj1412】[ZJOI2009]狼和羊的故事 网络流最小割