1
#yyds干货盘点# 解决剑指offer：最小的K个数
source link: https://blog.51cto.com/u_15488507/5285224
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
#yyds干货盘点# 解决剑指offer：最小的K个数
原创1.简述：
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
数据范围：，数组中每个数的大小
要求：空间复杂度 ，时间复杂度
[4,5,1,6,2,7,3,8],4
[1,2,3,4]
返回最小的4个数即可，返回[1,3,2,4]也可以
[1],0
[0,1,2,1,2],3
[0,1,1]
2.代码实现：
import java.util.*;
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<Integer>();
//排除特殊情况
if(k == 0 || input.length == 0)
return res;
//大根堆
PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
//构建一个k个大小的堆
for(int i = 0; i < k; i++)
q.offer(input[i]);
for(int i = k; i < input.length; i++){
//较小元素入堆
if(q.peek() > input[i]){
q.poll();
q.offer(input[i]);
}
}
//堆中元素取出入数组
for(int i = 0; i < k; i++)
res.add(q.poll());
return res;
}
}
public class Solution {
public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<Integer>();
//排除特殊情况
if(k == 0 || input.length == 0)
return res;
//大根堆
PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
//构建一个k个大小的堆
for(int i = 0; i < k; i++)
q.offer(input[i]);
for(int i = k; i < input.length; i++){
//较小元素入堆
if(q.peek() > input[i]){
q.poll();
q.offer(input[i]);
}
}
//堆中元素取出入数组
for(int i = 0; i < k; i++)
res.add(q.poll());
return res;
}
}
- 赞
- 收藏
- 评论
- 分享
- 举报
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK