leetcode哈希表之前K个高频元素序本文主要记录一下leetcode哈希

序本文主要记录一下leetcode哈希表之前K个高频元素
文章插图
题目给定一个非空的整数数组，返回其中出现频率前 k 高的元素。示例 1:输入: nums = [1,1,1,2,2,3], k = 2输出: [1,2]示例 2:输入: nums = [1], k = 1输出: [1]提示：你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。你可以按任意顺序返回答案。来源：力扣（LeetCode）链接：著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。题解【leetcode哈希表之前K个高频元素】class Solution {public int[] topKFrequent(int[] nums, int k) {if (nums == null || nums.length <= k) {return nums;}Map countMap = new HashMap<>();for (int num : nums) {countMap.put(num, countMap.getOrDefault(num, 0) + 1);}PriorityQueue queue=new PriorityQueue<>(new Comparator () {@Overridepublic int compare(Integer o1, Integer o2) {return countMap.get(o1)-countMap.get(o2);}});for (Map.Entry entry : countMap.entrySet()) {if (queue.size() < k) {queue.add(entry.getKey());continue;}if (countMap.get(queue.peek()) < entry.getValue()) {queue.poll();queue.add(entry.getKey());}}int[] result = new int[k];for (int i = 0; i < k; ++i) {result[i] = queue.poll();}return result;}}小结这里先借助HashMap来统计元素出现的频次，然后再借助PriorityQueue来维护topK的元素，最后取出来topK元素转换为数组。
doc

前K个高频元素