【LeetCode刷题日记】347.前k个高频元素

个人主页北极的代码欢迎来访作者简介java后端学习者❄️个人专栏苍穹外卖日记SSM框架深入JavaWeb✨命运的结局尽可永在不屈的挑战却不可须臾或缺摘要本文介绍了两种基于堆结构优先级队列的算法实现用于解决返回数组中出现频率前k高的元素问题。方法一使用大顶堆对所有元素进行排序后取前k个方法二采用更高效的小顶堆仅维护k个元素通过不断替换堆顶来保留高频元素。两种方法都先用哈希表统计元素频率再通过不同堆结构进行排序最终时间复杂度优于O(nlogn)。小顶堆实现更为优化仅需O(nlogk)时间复杂度适合处理大规模数据。题目背景347.前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]提示1 nums.length 105-104 nums[i] 104k的取值范围是[1, 数组中不相同的元素的个数]题目数据保证答案唯一换句话说数组中前k个高频元素的集合是唯一的进阶你所设计算法的时间复杂度必须优于O(n log n)其中n是数组大小。题目分析我们拿到这个题目题目要求是返回出现频率前k高的元素那我们首先想到的就是要记录给定数组中元素的出现次数然后我们要返回元素就不能仅仅记录次数要记录两个数据并且这个次数是和元素一一对应的这里我们能想到map集合很容易。记录完次数之后我们要返回前k个频率高的也就是说我们要对次数进行排序然后返回数组中的前k个的元素。对频率进行排序这里我们可以使用一种 容器适配器就是优先队列。这是整体的思路关于优先队列其实就是一个披着队列外衣的堆因为优先级队列对外接口只是从队头取元素从队尾添加元素再无其他取元素的方式看起来就是一个队列。而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢缺省情况下priority_queue利用max-heap大顶堆完成对元素的排序这个大顶堆是以vector为表现形式的complete binary tree完全二叉树。什么是堆呢堆是一棵完全二叉树树中每个结点的值都不小于或不大于其左右孩子的值。如果父亲结点是大于等于左右孩子就是大顶堆小于等于左右孩子就是小顶堆。所以大家经常说的大顶堆堆头是最大元素小顶堆堆头是最小元素如果懒得自己实现的话就直接用priority_queue优先级队列就可以了底层实现都是一样的从小到大排就是小顶堆从大到小排就是大顶堆。本题我们就要使用优先级队列来对部分频率进行排序。为什么不用快排呢 使用快排要将map转换为vector的结构然后对整个数组进行排序 而这种场景下我们其实只需要维护k个有序的序列就可以了所以使用优先级队列是最优的。此时要思考一下是使用小顶堆呢还是大顶堆有的同学一想题目要求前 K 个高频元素那么果断用大顶堆啊。那么问题来了定义一个大小为k的大顶堆在每次移动更新大顶堆的时候每次弹出都把最大的元素弹出去了那么怎么保留下来前K个高频元素呢。而且使用大顶堆就要把所有元素都进行排序那能不能只排序k个元素呢但其实大顶堆也能实现我们一起看看吧。所以我们要用小顶堆因为要统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆里积累的才是前k个最大元素。代码实现小顶堆实现先构建map集合来记录元素出现的频率循环遍历数组进行添加map.put(num, map.getOrDefault(num,0) 1);查找当前次数map.getOrDefault(num, 0)会去哈希表里查找num已经出现了几次。如果之前没出现过查不到就返回默认值0。次数加一把查到的次数可能是默认的0也可能是之前的数字加上1。存回哈希表map.put(num, ...)把更新后的次数重新存储到哈希表中键是num值是它最新的出现次数。然后我们就要用优先级队列对频率进行排序先构建一个优先队列PriorityQueueint[] pq new PriorityQueue((pair1, pair2) - pair1[1] - pair2[1]);PriorityQueueint[]创建了一个优先队列堆队列里每个元素都是一个长度为2的数组int[]这个数组的第一个位置pair[0]存数字本身第二个位置pair[1]存这个数字出现的次数频率。(pair1, pair2) - pair1[1] - pair2[1]这是一个比较规则Comparator决定了堆的排序方式。它比较两个数组的第二个元素即频率。如果pair1[1] - pair2[1]的结果是负数说明pair1的频率更小pair1会排在pair2前面。这个规则会让频率小的数组成为堆顶最先被取出的元素。然后我们进行添加有两个判断条件我们不需要添加所有因为用的是小顶堆当小于k个的时候直接添加下面的添加是核心逻辑大于k时我们要弹出队头也就是此时堆中频率最小的元素把新添加的放进去然后根据我们的规则继续进行比较排序// 堆内部自动执行 1. 把新元素放到末尾 → [[2,2], [1,3], [3,1]] 2. 比较 (3,1) 和它的父节点 (2,2): 调用你的规则compare([3,1], [2,2]) 1 - 2 -1 结果为负数 → [3,1] 应该排在 [2,2] 前面 所以交换 → [[3,1], [1,3], [2,2]] 3. 继续比较 (3,1) 和新的父节点没有→ 停止整体效果因为堆顶永远是当前堆里频率最小的那个数字所以当你维护这个堆的大小不超过k时堆里剩下的k个元素就是频率最大的前 k 个数字堆顶是第 k 大的频率。简单总结这行代码创建了一个按频率从小到大排序的小顶堆用于在遍历过程中随时淘汰频率不够大的数字最终留下频率最高的 k 个。然后我们把结果弹出从小顶堆中取出频率最高的前 k 个元素并按频率从高到低的顺序存入结果数组。// 从小顶堆弹出先得频率低的后得频率高的 弹出顺序: [3,1] → [2,2] → [1,3] // 从后往前填让频率高的在前面 ans数组: [0] [1] [2] i2: ans[2] poll() → [3,1] // 最后弹出得放最后 i1: ans[1] poll() → [2,2] i0: ans[0] poll() → [1,3] // 最后弹出高频率放最前 // 最终结果: ans [1, 2, 3] ← 频率从高到低题目答案//解法2基于小顶堆实现 public int[] topKFrequent2(int[] nums, int k) { MapInteger,Integer map new HashMap(); //key为数组元素值,val为对应出现次数 for (int num : nums) { map.put(num, map.getOrDefault(num, 0) 1); } //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数 //出现次数按从队头到队尾的顺序是从小到大排,出现次数最低的在队头(相当于小顶堆) PriorityQueueint[] pq new PriorityQueue((pair1, pair2) - pair1[1] - pair2[1]); for (Map.EntryInteger, Integer entry : map.entrySet()) { //小顶堆只需要维持k个元素有序 if (pq.size() k) { //小顶堆元素个数小于k个时直接加 pq.add(new int[]{entry.getKey(), entry.getValue()}); } else { if (entry.getValue() pq.peek()[1]) { //当前元素出现次数大于小顶堆的根结点(这k个元素中出现次数最少的那个) pq.poll(); //弹出队头(小顶堆的根结点),即把堆里出现次数最少的那个删除,留下的就是出现次数多的了 pq.add(new int[]{entry.getKey(), entry.getValue()}); } } } int[] ans new int[k]; for (int i k - 1; i 0; i--) { //依次弹出小顶堆,先弹出的是堆的根,出现次数少,后面弹出的出现次数多 ans[i] pq.poll()[0]; } return ans; } }用大顶堆实现主要就是添加的逻辑有所变化我们要对所有元素进行排序这是与小顶堆的最大区别小顶堆只需要维护k个因为弹出的自动是不符合的而大顶堆不能弹出弹出的是频率最高的是题目所需要的。堆结构按频率排序: (3, 1) ← 堆顶全局最大 / \ (2, 2) (1, 3)题目答案class Solution { //解法1基于大顶堆实现 public int[] topKFrequent1(int[] nums, int k) { MapInteger,Integer map new HashMap(); //key为数组元素值,val为对应出现次数 for (int num : nums) { map.put(num, map.getOrDefault(num,0) 1); } //在优先队列中存储二元组(num, cnt),cnt表示元素值num在数组中的出现次数 //出现次数按从队头到队尾的顺序是从大到小排,出现次数最多的在队头(相当于大顶堆) PriorityQueueint[] pq new PriorityQueue((pair1, pair2) - pair2[1] - pair1[1]); for (Map.EntryInteger, Integer entry : map.entrySet()) {//大顶堆需要对所有元素进行排序 pq.add(new int[]{entry.getKey(), entry.getValue()}); } int[] ans new int[k]; for (int i 0; i k; i) { //依次从队头弹出k个,就是出现频率前k高的元素 ans[i] pq.poll()[0]; } return ans; }复杂度分析方法时间复杂度空间复杂度大顶堆O(n k log n)O(n)小顶堆O(n log k)O(k)时间O(n log k)n个元素每个元素最多push/pop一次每次O(log k)空间O(k)堆只存储k个元素 哈希表O(n)结语如果对你有帮助请点赞关注收藏你的支持就是我最大的鼓励