堆

前 K 个高频元素

中等#347Java时间 O(n + u log k + k log k),u 为不同元素数空间 O(u)

题目要做什么

返回出现频率最高的 k 个元素。题目保证答案唯一,返回顺序不限。本课程将结果升序输出,便于验证。

题目示例输入nums = [1,1,1,2,2,3], k = 2
题目示例输出[1,2]

01 为什么这样做

先统计频次,再建立最多 k 项的小根堆。频次最低的候选位于根,数量超限时被淘汰。

始终成立的条件

堆保留已处理不同元素中频率最高的至多 k 项。

02 看见算法执行

动画与代码同步

修改输入,播放自己的例子

当前使用题目示例
修改输入会改变执行过程;预期输出用于核对结果。
数组 / nums步骤 1
执行状态
本次演示输出播放到最后查看

Solution.java参考解法
1class Solution {2    public int[] topKFrequent(int[] nums, int k) {3        Map<Integer, Integer> count = new HashMap<>();4        for (int value : nums) count.merge(value, 1, Integer::sum);5        PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) ->6            count.get(a).equals(count.get(b)) ? Integer.compare(a, b)7                : Integer.compare(count.get(a), count.get(b)));8        for (int value : count.keySet()) {9            heap.add(value);10            if (heap.size() > k) heap.remove();11        }12        int[] result = new int[k];13        for (int i = 0; i < k; i++) result[i] = heap.remove();14        Arrays.sort(result);15        return result;16    }17}

键盘控制:A 后退 · D 前进

编程练习

↑↓ 选择↵ 打开Pagefind 全文检索