Java 中的PriorityQueue是一个基于优先级堆的无界优先级队列。优先级队列的元素按照其自然顺序进行排序,或者根据构造队列时提供的 Comparator 进行排序,具体取决于所使用的构造方法。优先级队列不允许使用 null 元素。依靠自然顺序的优先级队列还不允许插入不可比较的对象(这样做可能导致 ClassCastException)。
此队列的头是按指定排序方式确定的最小元素。如果多个元素都是最小值,则头是其中一个元素——选择方法是任意的。队列获取操作 poll、 remove、peek 和 element 访问处于队列头的元素。
关于PriorityQueue的更多介绍可以查看API或者文章java 优先队列 PriorityQueue<E>。
选择最小的k个数可以用冒泡排序,复杂度为O(n*k),有点高。最经典的方法是使用最大堆,每次取数与堆顶的元素进行比较,如果堆顶元素大,则删除堆顶元素,并添加这个新数到堆中。
Java没有堆的实现,现场写也来不及,有的文献说用TreeSet,比如剑指offer,但是TreeSet是一个set,相同的数只能存一个,个人感觉不合适,相比之下,Java中的PriorityQueue倒是一个不错的选择。用PriorityQueue的实现的代码如下:
/**
* 用PriorityQueue实现选择最小的k个数
* @param array 数组
* @param k
* @return
*/
public int[] selectKmin(int[] array,int k){
int[] res = new int[k];
//创建一个降序排列的PriorityQueue,自定义比较器作为参数
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(k,new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}});
for(int i=0;i<array.length;i++){
if(priorityQueue.size()<k){
priorityQueue.add(array[i]);
}else{
int maxInQueue = priorityQueue.peek();
if(maxInQueue>array[i]){
priorityQueue.poll();
priorityQueue.add(array[i]);
}
}
}
//升序存放
for(int i=0;i<k;i++){
res[k-i-1] = priorityQueue.poll();
}
return res;
}
亲爱的读者:有时间可以点赞评论一下
月份 | 原创文章数 |
---|---|
202206 | 4 |
202205 | 2 |
202204 | 1 |
202203 | 11 |
202201 | 2 |
202108 | 7 |
202107 | 3 |
202106 | 16 |
202105 | 10 |
202104 | 16 |
202103 | 56 |
202102 | 14 |
202010 | 3 |
202009 | 3 |
202008 | 7 |
202007 | 7 |
202006 | 10 |
202005 | 11 |
202004 | 22 |
202003 | 52 |
202002 | 44 |
202001 | 83 |
201912 | 52 |
201911 | 29 |
201910 | 41 |
201909 | 99 |
201908 | 35 |
201907 | 73 |
201906 | 121 |
201811 | 1 |
201810 | 2 |
201804 | 1 |
201803 | 1 |
201802 | 1 |
201707 | 1 |
全部评论