核心内容摘要
嫩草文化传媒有限公司：破局与新生，探寻文娱产业的勃勃生机
文章目录前言
数组中的第K个大的元素
题目
代码
例子
前k个高频元素
题目
代码
理解
PriorityQueue的排序规则
offer方法和add方法的区别
例子
数据流中的中位数
题目
代码
例子前言本文记录力扣Hot100里面关于堆的三道题包括常见解法和一些关键步骤理解也有例子便于大家理解
数组中的第K个大的元素
题目给定整数数组 nums 和整数 k请返回数组中第 k 个最大的元素。
请注意你需要找的是数组排序后的第 k 个最大的元素而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:输入: [3,2,1,5,6,4], k 2输出: 5示例 2:输入: [3,2,3,1,2,4,5,5,6], k 4输出:
代码classSolution{publicintfindKthLargest(int[]nums,intk){QueueIntegerqueuenewPriorityQueue();// new PriorityQueue((a, b) - (b - a)); 如果这样写就是大顶堆for(inti0;inums.length;i){queue.offer(nums[i]);if(queue.size()k){queue.poll();}}returnqueue.poll();}}QueueInteger queue new PriorityQueue();Java的PriorityQueue默认是小顶堆堆顶元素是整个堆中最小的元素
例子输入数组nums [3,2,1,5,6,4]要找的目标第2个最大的元素预期结果是5核心逻辑用小顶堆维护当前最大的k个元素超过k个就移除堆里最小的元素最终堆顶就是第k大元素。
初始化创建一个空的小顶堆queue。
遍历第一个元素 3把3加入堆堆内元素为 [3]小顶堆堆顶是3。
堆的大小是1小于k2不做移除操作。
遍历第二个元素 2把2加入堆堆会自动调整为小顶堆堆内元素为 [2, 3]堆顶是2。
堆的大小是2等于k2不做移除操作。
遍历第三个元素 1把1加入堆堆内元素变为 [1, 3, 2]堆顶是1。
堆的大小是3超过了k2需要移除堆顶最小的元素1。
移除后堆内元素回到 [2, 3]堆顶是2。
遍历第四个元素 5把5加入堆堆内元素变为 [2, 3, 5]堆顶是2。
堆的大小是3超过k2移除堆顶的2。
移除后堆内元素变为 [3, 5]堆顶是3。
遍历第五个元素 6把6加入堆堆内元素变为 [3, 5, 6]堆顶是3。
堆的大小是3超过k2移除堆顶的3。
移除后堆内元素变为 [5, 6]堆顶是5。
遍历第六个元素 4把4加入堆堆会自动调整为小顶堆堆内元素变为 [4, 6, 5]堆顶是4。
堆的大小是3超过k2移除堆顶的4。
移除后堆内元素回到 [5, 6]堆顶是5。
最终结果遍历完所有元素后堆里只剩下数组中最大的2个元素5和6小顶堆的堆顶是5。
执行return queue.poll();弹出堆顶元素5这就是数组中第2个最大的元素和预期结果一致。
前k个高频元素
题目给你一个整数数组 nums 和一个整数 k 请你返回其中出现频率前 k 高的元素。
你可以按 任意顺序 返回答案。
示例 1输入nums [1,1,1,2,2,3], k 2输出[1,2]示例 2输入nums [1], k 1输出[1]示例 3输入nums [1,2,1,2,1,2,3,1,3,2], k 2输出[1,2]
代码步骤初始化结果数组创建长度为k的数组res用于存储最终的前k个高频元素。
统计元素频率初始化HashMap以数组元素为key、元素出现次数为value遍历数组用getOrDefault方法更新每个元素的频率不存在则默认0存在则1。
初始化小顶堆创建存储Map.Entry键值对的优先队列自定义比较器按value频率升序排序形成小顶堆频率最小的在堆顶。
筛选前k个高频元素遍历HashMap的所有键值对将每个键值对加入小顶堆若堆的大小超过k移除堆顶元素当前堆中频率最小的元素确保堆中始终只保留遍历过的元素里频率最高的k个。
提取结果并返回遍历k次依次弹出堆顶的键值对取出其中的key元素值存入结果数组返回结果数组数组内即为频率前k高的元素。
classSolution{publicint[]topKFrequent(int[]nums,intk){// 前k个高频元素,小顶堆int[]resnewint[k];// 统计每个元素的频率存储到Map中key是元素值value是元素的频率MapInteger,IntegermapnewHashMap();for(intnum:nums){map.put(num,map.getOrDefault(num,
0)
;}// 使用小顶堆堆中存储的是 Map的key,value 键值对// 并且排序规则是以value为比较, 即以元素的频率大小为比较QueueMap.EntryInteger,IntegerqueuenewPriorityQueue((o1,o
-o
getValue()-o
getValue()// 注意这样写是小顶堆反过来就是大顶堆);for(Map.EntryInteger,Integerentry:map.entrySet()){queue.add(entry);if(queue.size()k){queue.poll();}}// 将堆内剩余k个元素结果放到数组中返回。
剩余k个元素即频率最高的k个元素for(inti0;ik;i){res[i]queue.poll().getKey();// 由于堆中存的是键值对所以这里需要getKey}returnres;}}
理解
PriorityQueue的排序规则QueueMap.EntryInteger,IntegerqueuenewPriorityQueue((o1,o
-o
getValue()-o
getValue()// 注意这样写是小顶堆反过来就是大顶堆);场景1存储基本类型Integer、Double 等// 这行代码默认小根堆QueueIntegerqueuenewPriorityQueue();queue.add(
;queue.add(
;queue.add(
;System.out.println(queue.peek());// 输出 1堆顶是最小元素PriorityQueue 对Integer等基本类型的包装类默认按照自然顺序升序排列所以堆顶是最小值也就是小根堆。
等价于手动写比较器new PriorityQueue((a, b) - a - b)a - b 结果为正则a排在b后面最小的在堆顶。
场景2存储自定义类型如 Map.Entry// 自定义小根堆按value升序QueueMap.EntryInteger,IntegerqueuenewPriorityQueue((o1,o
-o
getValue()-o
getValue());因为Map.Entry不是基本类型没有默认的“自然顺序”所以必须手动指定比较器。
这里的o
getValue()-o
getValue()本质和a - b是同一个逻辑按value升序排列value最小的在堆顶也就是按value排序的小根堆。
offer方法和add方法的区别add()和offer()的核心功能是一样的都是向队列堆中添加元素。
两者的唯一区别在于添加失败时的处理方式——一个抛异常一个返回布尔值。
方法定义与失败处理Java 官方规范方法成功返回值失败场景队列满了失败处理方式add(E e)true队列容量达到上限抛出IllegalStateException异常offer(E e)true/false队列容量达到上限返回false不抛异常静默失败
结合你的使用场景PriorityQueue你在找第k大元素、数据流中位数等代码中用到的PriorityQueue是无界队列理论上没有容量上限只要内存足够就能一直加元素所以调用add()永远返回true永远不会触发“队列满”的失败场景也就永远不会抛异常调用offer()永远返回true同样不会触发失败场景。
结论在PriorityQueue中add()和offer()完全等价你可以随便换用比如把代码里的queue.offer(nums[i])改成queue.add(nums[i])运行结果不会有任何变化。
什么时候能看出区别有界队列示例只有在有界队列比如ArrayBlockingQueue创建时指定固定容量中才能体现两者的差异// 创建一个容量为2的有界队列QueueIntegerqueuenewArrayBlockingQueue(
;queue.add(
;// 成功返回truequeue.offer(
;// 成功返回true// 尝试添加第三个元素queue.add(
;// 失败直接抛出 IllegalStateException 异常booleanresultqueue.offer(
;// 失败返回false不抛异常
总结核心区别添加失败时add()抛异常offer()返回false无界队列如 PriorityQueue中两者完全等价有界队列中offer()更适合优雅处理“队列满”的情况。
例子输入数组nums [1,1,1,2,2,3]目标找前k2个高频元素预期结果
2步骤1初始化结果数组创建长度为2的数组res此时res [0, 0]初始值。
步骤2统计元素频率遍历数组[1,1,1,2,2,3]用HashMap统计每个元素的出现次数遍历1map中1的频率从0→1遍历1map中1的频率从1→2遍历1map中1的频率从2→3遍历2map中2的频率从0→1遍历2map中2的频率从1→2遍历3map中3的频率从0→1最终map内容{13, 22, 31}1出现3次2出现2次3出现1次。
步骤3初始化小顶堆创建存储Map.Entry的优先队列比较规则为“按value频率升序”此时堆为空。
步骤4筛选前k个高频元素遍历map的3个键值对逐个加入堆并维护堆大小不超过2处理键值对(1,
加入堆堆内元素[(1,
]堆大小1≤2不移除元素处理键值对(2,
加入堆堆自动调整为小顶堆按频率升序堆内元素[(2,
, (1,
]堆顶是频率2的2堆大小22不移除元素处理键值对(3,
加入堆堆内元素[(3,
, (1,
, (2,
]堆大小32移除堆顶元素频率最小的(3,
堆内剩余[(2,
, (1,
]。
步骤5提取结果并返回遍历2次弹出堆顶元素并提取key存入res第一次弹出堆顶(2,
提取key2res[0] 2第二次弹出堆顶(1,
提取key1res[1] 1最终res [2, 1]返回该数组顺序不影响只要是前2个高频元素即可。
数据流中的中位数
题目中位数是有序整数列表中的中间值。
如果列表的大小是偶数则没有中间值中位数是两个中间值的平均值。
例如 arr [2,3,4] 的中位数是 3 。
例如 arr [2,3] 的中位数是 (2
/ 2
5 。
实现 MedianFinder 类:MedianFinder() 初始化 MedianFinder 对象。
void addNum(int num) 将数据流中的整数 num 添加到数据结构中。
double findMedian() 返回到目前为止所有元素的中位数。
与实际答案相差 10(-
以内的答案将被接受。
示例 1输入[“MedianFinder”, “addNum”, “addNum”, “findMedian”, “addNum”, “findMedian”][[], [1], [2], [], [3], []]输出[null, null, null,
5, null,
0]解释MedianFinder medianFinder new MedianFinder();medianFinder.addNum(
; // arr [1]medianFinder.addNum(
; // arr [1, 2]medianFinder.findMedian(); // 返回
5 ((1
/
medianFinder.addNum(
; // arr[1, 2, 3]medianFinder.findMedian(); // return
2.
代码
初始化构造方法定义两个优先队列queMin为大顶堆存储较小一半元素堆顶是该部分最大值queMax为小顶堆存储较大一半元素堆顶是该部分最小值。
添加元素addNum 方法判定归属若数字≤queMin堆顶或queMin为空放入queMin否则放入queMax。
平衡堆大小若queMin比queMax多超过1个将queMin堆顶移到queMax若queMax大小超过queMin将queMax堆顶移到queMin最终保证queMin大小 queMax大小 或queMin大小 queMax大小1。
查找中位数findMedian 方法若元素总数为奇数queMin更大中位数是queMin堆顶若元素总数为偶数两堆大小相等中位数是两堆顶数值的平均值。
classMedianFinder{// 大顶堆存储较小的一半元素堆顶是这部分的最大值PriorityQueueIntegerqueMin;// 小顶堆存储较大的一半元素堆顶是这部分的最小值PriorityQueueIntegerqueMax;// 初始化堆queMin大顶堆queMax小顶堆publicMedianFinder(){queMinnewPriorityQueueInteger((a,b)-(b-a));queMaxnewPriorityQueueInteger((a,b)-(a-b));}// 添加元素维持堆平衡queMin.size() queMax.size() 或 queMin.size() queMax.size()1publicvoidaddNum(intnum){// 元素归入较小半区queMinif(queMin.isEmpty()||numqueMin.peek()){queMin.offer(num);// 平衡queMin超出queMax1时移堆顶到queMaxif(queMax.size()1queMin.size()){queMax.offer(queMin.poll());}}else{// 元素归入较大半区queMaxqueMax.offer(num);// 平衡queMax超过queMin时移堆顶到queMinif(queMax.size()queMin.size()){queMin.offer(queMax.poll());}}}// 获取中位数奇数取queMin堆顶偶数取两堆顶平均值publicdoublefindMedian(){if(queMin.size()queMax.size()){returnqueMin.peek();}return(queMin.peek()queMax.peek())/
0;}}
例子以5 → 2 → 7 → 1 → 9为例数据流添加顺序5 → 2 → 7 → 1 → 9规则queMin大顶堆存较小半区、queMax小顶堆存较大半区保证queMin.size()queMax.size()或queMin.size()queMax.size()1初始化queMin大顶堆为空queMax小顶堆为空。
步骤1添加元素 5判定归属queMin为空将5放入queMin平衡堆大小queMin.size()1queMax.size()0符合规则无需调整当前堆状态queMin[5]堆顶
queMax[]查中位数总数奇数中位数5。
步骤2添加元素 2判定归属2 ≤queMin堆顶5放入queMin平衡堆大小queMin.size()2queMax.size()0queMin比queMax多2个超出规则将queMin堆顶5移到queMax当前堆状态queMin[2]堆顶
queMax[5]堆顶5查中位数总数偶数中位数(
/
2
5。
步骤3添加元素 7判定归属7 queMin堆顶2放入queMax平衡堆大小queMax.size()2queMin.size()1将queMax堆顶5移到queMin当前堆状态queMin[5,2]大顶堆堆顶
queMax[7]堆顶7查中位数总数奇数中位数5。
步骤4添加元素 1判定归属1 ≤queMin堆顶5放入queMin平衡堆大小queMin.size()3queMax.size()1queMin比queMax多2个将queMin堆顶5移到queMax当前堆状态queMin[2,1]堆顶
queMax[5,7]堆顶5查中位数总数偶数中位数(
/
2
5。
步骤5添加元素 9判定归属9 queMin堆顶2放入queMax平衡堆大小queMax.size()3queMin.size()2将queMax堆顶5移到queMin当前堆状态queMin[5,1,2]大顶堆堆顶
queMax[7,9]堆顶7查中位数总数奇数中位数5。
如果本篇文章对您有帮助可以点赞收藏或评论哦关注主包不迷路让我们一起向前进步吧