hello大家好呀，本博客目的在于记录暑假学习打卡，后续会整理成一个专栏，主要打算在暑假学习完数据结构，因此会发一些相关的数据结构实现的博客和一些刷的题，个人学习使用，也希望大家多多支持，有不足之处也请指出。本篇只讲解OJ题，关于知识点的博客稍后发出，希望大家多多支持。
面试题17.14，最小k个数
思路一：构建小堆
我们知道已经学习过优先级队列PriorityQueue，并且知道它底层就是堆，并且默认是小堆存放，那么，第一种思路便很清晰了，用数据集合中前K个元素来建堆，然后获取堆中前k个元素
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] ret=new int[k];
PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();
for (int i = 0; i <arr.length ; i++) {
priorityQueue.offer(arr[i]);
}
for (int i = 0; i < k; i++) {
ret[i]=priorityQueue.poll();
}
return ret;
}
}思路二：构建大堆
可以通过构建小堆解题，那么同样也可以使用大堆，第二个思路便是自己实现比较方法构建大堆，将剩余的N-K个元素依次与堆顶元素来比较，如果小于栈顶元素则替换堆顶元素，然后将剩余N-K个元素依次与堆顶元素比完之后，堆中剩余的K个元素就是所求的前K个最小。
class Solution {
public int[] smallestK(int[] arr, int k) {
if(k<=0){
return new int[0];
}
int[] ret=new int[k];
PriorityQueue<Integer> priorityQueue=new PriorityQueue<>(new com());
for (int i = 0; i <k; i++) {
priorityQueue.offer(arr[i]);
}
for (int j = k; j <arr.length; j++) {
if(arr[j]<priorityQueue.peek()){
priorityQueue.poll();
priorityQueue.offer(arr[j]);
}
}
for (int i = 0; i < k; i++) {
ret[i]=priorityQueue.poll();
}
return ret;
}
}
class com implements Comparator<Integer>{
@Override
public int compare(Integer t2, Integer t1) {
return t1-t2;
}
}以上就是本期博客全部内容啦，明天考完科二会会把PriorityQueue详解发出来，感谢大家支持
