最小的K个数(手写大顶堆和用优先级队列比较)

简介: 输入n个整数,找出其中最小的K个数。

题目描述

输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4。




      第一种方法,用优先级队列构造出最大堆,然后不断更新最大堆,每次只和堆顶比,如果比堆顶小,删除堆顶,新数入堆。但是这里利用集合并不好,手写最大堆会比这个更优,因为在超过k个数的时候,优先级队列需要poll和offer(或者add)操作,poll会下沉恢复堆有序源码思路:将数组最后一个元素赋给堆顶,size-1,然后从堆顶往下一个个比较,相当于把堆顶往下沉,然后到合适位置,堆顶下沉只会赋值一次,并不是下沉的时候比较交换),offer会上升恢复堆有序源码思路:从堆底往上一个个比较,相当于把堆底往上浮,堆底上浮只会赋值一次到合适位置,并不是上浮的时候比较交换),而如果手写堆实现的话,仅仅只需要将堆顶元素替换再下沉,就没有了上升恢复堆有序的环节如果是100W个数找最小的5个数,假如情况比较糟糕,每次都需要更新最大堆堆顶,如果那么使用PriorityQueue将要多做999995(99W近100W)次上升恢复堆有序的操作。可以看一下PriorityQueue的源码就知道。

并且最后迭代的时候要么foreach要么iterator,本质就是iterator迭代。为什么不用for循环去list.add(queue.poll())?虽然也可以出结果,但是queue的poll方法会有下沉恢复堆有序操作,而iterator不会,仅仅是遍历数组。最后返回的ArrayList是满足要求的数字但不一定有序(因为数组堆不一定有序),返回这个ArrayList,最后判题系统应该会排序后来判断结果对不对。

PS:优先级队列的传入比较器参数new Comparator是需要在上浮和下沉的时候将回调我们重写的compare方法来构建出最大最小堆。


       PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>(){

           public int compare(Integer i1, Integer i2) {

               return i2.compareTo(i1);

           }

       });


这里如果i1.compareTo(i2)那么就是构建的小顶堆(其实默认也是小顶堆),如果i2.compareTo(i1)就是大顶堆。


AC代码:


importjava.util.ArrayList;
importjava.util.Comparator;
importjava.util.Iterator;
importjava.util.PriorityQueue;
publicclassSolution {
publicArrayList<Integer>GetLeastNumbers_Solution(int [] input, intk) {
ArrayList<Integer>list=newArrayList<Integer>();
// [4,5,1,6,2,7,3,8],0if (input==null||k>input.length||k<=0)    returnlist;
PriorityQueue<Integer>queue=newPriorityQueue<Integer>(newComparator<Integer>(){
publicintcompare(Integeri1, Integeri2) {
returni2.compareTo(i1);
            }
        });
intlen=input.length;
for (inti=0; i<len; ++i) {
if (queue.size() !=k) {
queue.offer(input[i]);
            } elseif (queue.peek() >input[i]) {
queue.poll();
queue.offer(input[i]);
            }
        }
Iterator<Integer>it=queue.iterator();
while (it.hasNext()) {
list.add(it.next());
        }
returnlist;
    }
}

image.gif

第二种方法:手写最大堆实现(绝对比PriorityQueue优)

AC代码:


importjava.util.ArrayList;
publicclassSolution {
publicArrayList<Integer>GetLeastNumbers_Solution(int[] input, intk) {
ArrayList<Integer>list=newArrayList<Integer>();
// [4,5,1,6,2,7,3,8],0if (input==null||k>input.length||k<=0)
returnlist;
int[] target=newint[k];
intlen=input.length;
for (inti=0; i<len; ++i) {
if (i<k) {
target[i] =input[i];
heapInsertSiftUp(target, i, target[i]);
            } else {
if (target[0] >input[i]) { // 最大堆下沉target[0] =input[i];
siftDown(target, 0, target[0]);
// 相比优先级队列,这里不会offer操作(里面有上浮),少了一步上浮调整,效率高了不止一丁点                }
            }
        }
for (inti=0; i<k; ++i) {
list.add(target[i]);
        }
returnlist;
    }
privatevoidheapInsertSiftUp(int[] target, intindex, intx) {
while (index>0) {
intparent= (index-1) >>>1;
if (greater(x, target[parent])) {
target[index] =target[parent]; // 往下拉,避免直接上浮覆盖前面的值index=parent;
            } else {
break;
            }
        }
target[index] =x;
    }
privatebooleangreater(inti, intj) {
returni>j;
    }
privatevoidsiftDown(int[] target, intk, intx) {
inthalf=target.length>>>1;
while (k<half) {
intchild= (k<<1) +1; // 默认先左孩子intbig=target[child];
intright=child+1;
if (right<target.length&&greater(target[right], big)) {
big=target[right];
child=right; // 可以直接一步big = target[child = right];            }
if (greater(x, big)) // x比子节点中的最大值还大,已经是大顶堆了break; // 往上拉不动了,准备退出把最初堆顶的结点赋值到上一个结点target[k] =big; // 往上拉k=child;
        }
target[k] =x;
    }
}

image.gif



==============Talk is cheap, show me the code===============

目录
相关文章
|
机器学习/深度学习 人工智能 算法
【机器学习】深度神经网络(DNN):原理、应用与代码实践
【机器学习】深度神经网络(DNN):原理、应用与代码实践
2622 1
|
12月前
|
数据采集 安全 API
数据治理:实现原始数据不出域,确保数据可用不可见的创新策略
在数字化时代,数据成为企业宝贵资产,驱动业务决策与创新。然而,数据量激增和流通频繁带来了安全和管理挑战。“原始数据不出域,数据可用不可见”的治理理念应运而生,通过数据脱敏、沙箱技术和安全多方计算等手段,确保数据安全共享与高效利用。这一理念已广泛应用于金融、医疗等行业,提升了数据价值和企业竞争力。
1804 0
|
存储 缓存 IDE
深度探索Linux操作系统 —— 构建initramfs
深度探索Linux操作系统 —— 构建initramfs
959 5
|
Java
Java中的匿名内部类(看这篇就够了)
Java中的匿名内部类(看这篇就够了)
1721 0
|
存储 编解码 API
阿里云视频点播VoD
阿里云视频点播VoD
1023 0
|
存储 C++
链表操作:插入、删除与遍历
(笔者画图不易呜呜)链表是一种基本的数据结构,它可以用来存储一系列的元素,并且支持灵活的插入、删除操作。在计算机科学中,链表常常用于构建更复杂的数据结构,如栈、队列以及图等。
527 0
|
Oracle NoSQL 关系型数据库
面向对象程序设计原则——依赖倒置原则(DIP)
面向对象程序设计原则——依赖倒置原则(DIP)
355 0
|
消息中间件 存储 Java
「Spring和Kafka」Kafka整合Spring 深入挖掘第2部分:Kafka和Spring Cloud Stream
「Spring和Kafka」Kafka整合Spring 深入挖掘第2部分:Kafka和Spring Cloud Stream
|
存储 NoSQL 算法
分布式系统唯一ID生成方案汇总
分布式系统唯一ID生成方案汇总
598 0
分布式系统唯一ID生成方案汇总
|
网络协议 网络虚拟化 Windows
测试vpn设备 带宽,丢包率windows使用iperf3
iPerf3是用于主动测试IP网络上最大可用带宽的工具。它支持时序、缓冲区、协议(TCP,UDP,SCTP与IPv4和IPv6)有关的各种参数。对于每次测试,它都会详细的带宽报告,延迟抖动和数据包丢失。
1310 0
测试vpn设备 带宽,丢包率windows使用iperf3