【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;
    }
}

原文地址：https://blog.csdn.net/2401_88859777/article/details/145128383

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！