【Leetcode 热题 100】347. 前 K 个高频元素

问题背景

给你一个整数数组 $nums$ 和一个整数 $k$，请你返回其中出现频率前 $k$ 高的元素。你可以按 任意顺序 返回答案。

数据约束

• $1\le nums.length\le 10^5$
• $k$ 至少为 $1$，且不会超过数组中不相同的元素的个数
• 题目数据保证答案唯一，换句话说，数组中前 $k$ 个高频元素的集合是唯一的

解题过程

由于要求前 $k$ 个，随机选择算法就没有太明显的优势了，首先想到用堆。
实际上使用堆来找多个符合条件的元素的过程，时间复杂度也会达到 $O(NlogN)$ 这样的级别，和排序大致相当，所以这题也完全可以先排序来解决。

具体实现

class Solution {public int[] topKFrequent(int[] nums, int k) {// 元素范围不定，可能有负数，不能用自定义的数组来模拟哈希表Map<Integer, Integer> map = new HashMap<>();for(int num : nums) {map.merge(num, 1, Integer::sum);}// 创建一个自定义排序规则的堆Queue<int[]> heap = new PriorityQueue<>((o1, o2) -> o2[1] - o1[1]);// 遍历哈希表，并将元素按要求添加到堆中for(Map.Entry<Integer, Integer> entry : map.entrySet()) {int item = entry.getKey();int times = entry.getValue();heap.offer(new int[]{item, times});}int[] res = new int[k];// 元素依次出堆，找到频率前 k 的那些，组装成答案for(int i = 0; i < k; i++) {res[i] = heap.poll()[0];}return res;}
}