题目

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

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:

输入: nums = [1], k = 1
输出: [1]

 

提示：

• 1 <= nums.length <= 105
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

 

进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

标签: 数组 哈希表 分治 桶排序 计数 快速选择 排序 堆（优先队列）

相似题目

• 中等: 统计词频
• 中等: 数组中的第K个最大元素
• 中等: 根据字符出现频率排序
• 中等: 分割数组为连续子序列
• 中等: 前K个高频单词
• 中等: 最接近原点的 K 个点

代码

public class TopKFrequent {

    class Solution {

        // 经典top key问题
        public int[] topKFrequent(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k <= 0) {
                return new int[0];
            }
            // 结果集
            int[] result = new int[k];
            // 先统计
            Map<Integer, Integer> memo = new HashMap<>();
            for (int num : nums) {
                memo.put(num, memo.getOrDefault(num, 0) + 1);
            }
            // 小顶堆，使用优先队列
            PriorityQueue<int[]> priorityQueue = new PriorityQueue<>(((o1, o2) -> o1[1] - o2[1]));
            // 遍历统计结果
            memo.forEach((num, count) -> {
                // 如果堆中元素个数小于k，直接入堆
                if (priorityQueue.size() < k) {
                    priorityQueue.offer(new int[]{num, count});
                } else {
                    // 如果堆中元素个数等于k，且当前元素的出现次数大于堆顶元素的出现次数，弹出堆顶元素，将当前元素入堆
                    if (count > priorityQueue.peek()[1]) {
                        priorityQueue.poll();
                        priorityQueue.offer(new int[]{num, count});
                    }
                }
            });
            for (int i = 0; i < k; i++) {
                int[] value = priorityQueue.poll();
                if (value != null && value.length > 0) {
                    result[i] = value[0];
                }
            }
            return result;
        }

    }

}

链接

• leetcode347. 前 K 个高频元素