昆明专业网站建设的公司,如何自定义wordpress的登录页面,小程序平台源码,怎么看网站开发的技术2024.1.23(347.前k个高频元素) 思路 这道题目主要涉及到如下三块内容#xff1a;
1.要统计元素出现频率 2.对频率排序 3.找出前K个高频元素 首先统计元素出现的频率#xff0c;这一类的问题可以使用map来进行统计。
然后是对频率进行排序#xff0c;这里我们可以使用一种…2024.1.23(347.前k个高频元素) 思路 这道题目主要涉及到如下三块内容
1.要统计元素出现频率 2.对频率排序 3.找出前K个高频元素 首先统计元素出现的频率这一类的问题可以使用map来进行统计。
然后是对频率进行排序这里我们可以使用一种 容器适配器就是优先级队列。
什么是优先级队列呢
其实就是一个披着队列外衣的堆因为优先级队列对外接口只是从队头取元素从队尾添加元素再无其他取元素的方式看起来就是一个队列。
而且优先级队列内部元素是自动依照元素的权值排列。那么它是如何有序排列的呢
缺省情况下priority_queue利用max-heap大顶堆完成对元素的排序这个大顶堆是以vector为表现形式的complete binary tree完全二叉树。
什么是堆呢
堆是一棵完全二叉树树中每个结点的值都不小于或不大于其左右孩子的值。 如果父亲结点是大于等于左右孩子就是大顶堆小于等于左右孩子就是小顶堆。
所以大家经常说的大顶堆堆头是最大元素小顶堆堆头是最小元素如果懒得自己实现的话就直接用priority_queue优先级队列就可以了底层实现都是一样的从小到大排就是小顶堆从大到小排就是大顶堆。
本题我们就要使用优先级队列来对部分频率进行排序。
为什么不用快排呢 使用快排要将map转换为vector的结构然后对整个数组进行排序 而这种场景下我们其实只需要维护k个有序的序列就可以了所以使用优先级队列是最优的。
此时要思考一下是使用小顶堆呢还是大顶堆
有的同学一想题目要求前 K 个高频元素那么果断用大顶堆啊。
那么问题来了定义一个大小为k的大顶堆在每次移动更新大顶堆的时候每次弹出都把最大的元素弹出去了那么怎么保留下来前K个高频元素呢。
而且使用大顶堆就要把所有元素都进行排序那能不能只排序k个元素呢
所以我们要用小顶堆因为要统计最大前k个元素只有小顶堆每次将最小的元素弹出最后小顶堆里积累的才是前k个最大元素。
寻找前k个最大元素流程如图所示图中的频率只有三个所以正好构成一个大小为3的小顶堆如果频率更多一些则用这个小顶堆进行扫描
// 定义一个名为 Solution 的类 class Solution { // 定义一个公共方法返回一个整数数组该方法接收两个参数一个整数数组 nums 和一个整数 k public int[] topKFrequent(int[] nums, int k) { // 创建一个优先级队列 pq用于存储整数数组队列的排序规则是从大到小根据数组的第二个元素 // 这是为了避免使用复杂的 API 操作因为优先级队列的特性是队首元素总是最小的或者最大的取决于排序规则 PriorityQueueint[] pq new PriorityQueue((o1, o2) - o1[1] - o2[1]); // 创建一个大小为 k 的整数数组 res用于存储结果 int[] res new int[k]; // 创建一个哈希映射 map用于记录每个元素的出现次数 MapInteger, Integer map new HashMap(); // 遍历输入数组 nums统计每个元素的出现次数并存储在哈希映射 map 中 for(int num : nums) map.put(num, map.getOrDefault(num, 0) 1); // 遍历哈希映射的 entrySet将每个元素及其出现次数转化为数组形式并加入优先级队列 pq for(var x : map.entrySet()) { int[] tmp new int[2]; tmp[0] x.getKey(); // 当前元素的键数字 tmp[1] x.getValue(); // 当前元素的值出现次数 pq.offer(tmp); // 将转化后的数组加入优先级队列 pq // 如果优先级队列的大小超过了 k则移除队首元素即出现次数最少的元素 if(pq.size() k) { pq.poll(); } } // 从优先级队列 pq 中取出前 k 个元素即出现次数最多的 k 个元素并存入结果数组 res for(int i 0; i k; i ) { res[i] pq.poll()[0]; // 取出的数组的第一个元素是数字本身所以用 poll()[0] 获取这个数字 } // 返回结果数组 res return res;
} } 这个代码的主要思路是利用优先级队列来存储出现次数最多的k个元素。由于优先级队列的特性我们可以在添加新元素时保持队列的大小不超过k同时保证了队首始终是出现次数最多的元素。这样最后从队列中取出的就是出现次数最多的k个元素。
