贪心与堆中等1 种解法

#347前 K 个高频元素

返回整数数组中出现频率最高的 k 个不同元素，答案顺序不限。

#数组#哈希表#优先队列

解题主线

先用哈希表把原数组压缩为不同元素及其频次，再按频次建立最大堆。

堆节点同时保存 value 与 frequency，每次弹出当前剩余频次最高的元素。

解法 1：频次表加最大堆

统计每个值的出现次数，把 [频次, 值] 放入最大堆，再弹出 k 次。

时间复杂度

O(n + m log m)，m 为不同元素数

空间复杂度

O(m)

347. 前 K 个高频元素 · 频次表加最大堆

java

import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;

final class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> frequencies = new HashMap<>();
        for (int value : nums) {
            frequencies.merge(value, 1, Integer::sum);
        }
        if (k < 0 || k > frequencies.size()) {
            throw new IllegalArgumentException("k exceeds the number of distinct values");
        }

        PriorityQueue<int[]> maximums = new PriorityQueue<>((first, second) -> {
            int byFrequency = Integer.compare(second[0], first[0]);
            return byFrequency != 0
                ? byFrequency
                : Integer.compare(second[1], first[1]);
        });
        for (Map.Entry<Integer, Integer> entry : frequencies.entrySet()) {
            maximums.offer(new int[] {entry.getValue(), entry.getKey()});
        }

        int[] answer = new int[k];
        for (int i = 0; i < k; i++) {
            answer[i] = maximums.remove()[1];
        }
        return answer;
    }
}

统计每个值的出现次数，把 [频次, 值] 放入最大堆，再弹出 k 次。

边界与易错点

旧比较器使用频次或元素值相减，极端整数可能溢出并破坏比较器契约；应使用 Integer.compare。
k 针对不同元素数量，不能大于频次表大小。
题目允许任意答案顺序，不应依赖并列频次元素的固定次序。

整理来源

由旧仓库源码复核、去重并整理；展示代码已按 Java 21 语义修正明显问题。

leetcode/src/main/java/medium/Q347_topKFrequent.java