LeetCode--347.前 K 个高频元素（栈和队列）

张开发
• 2026/4/15 22:08:20 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode--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是数组大小。解题思路该题借助Mapkey为numvalue为出现次数来统计出现的数字次数。借助PriorityQueue优先级队列大顶堆/小顶堆的一种实现方式来对Map中的元素进行频率排序。大顶堆的定义1、大顶堆是一棵完全二叉树每个父节点的值都大于或等于其子节点的值。2、在堆结构中堆顶根节点始终是整个集合中的最大元素。代码classSolution{// 基于大顶堆实现publicint[]topKFrequent(int[]nums,intk){// 用Map来存放数和频率,key为数,value为频率MapInteger,IntegermapnewHashMap();for(intnum:nums){// 从1开始计数map.put(num,map.getOrDefault(num,0)1);}// 使用PriorityQueue实现大顶堆// Comparator接口默认返回o1-o2,在PriorityQueue中默认为小顶堆// 这里重写Comparator接口的compare方法(o1, o2) - o2[1] - o1[1],频率相减// 变成大顶堆排序PriorityQueueint[]pqnewPriorityQueue((o1,o2)-o2[1]-o1[1]);for(Map.EntryInteger,Integerentry:map.entrySet()){// 向PriorityQueue中插入数据pq.add(newint[]{entry.getKey(),entry.getValue()});}int[]resultnewint[k];for(inti0;ik;i){// 将前k个高频率插入返回数组result[i]pq.poll()[0];}returnresult;}}

更多文章