栈与队列——347. 前 K 个高频元素

向着百万年薪努力的小赵

发布于 2022-12-02 11:08:37

2270

发布于 2022-12-02 11:08:37

文章被收录于专栏：小赵的Java学习

1 题目描述

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

2 题目示例

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

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

3 题目提示

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

4 思路

队列： 哈希的作用是记录每个元素的出现次数。遍历元素，当优先队列中元素个数小于k，则一直入队，当元素个数为k，新需要入队列的元素需要和队尾的元素比较出现次数，决定队列是否弹出元素，新元素入队。遍历完成后，将队列中的元素移到数组即可。堆：首先遍历整个数组，并使用哈希表记录每个数字出现的次数，并形成一个「出现次数数组」。找出原数组的前k个高频元素，就相当于找出「出现次数数组」的前k大的值。最简单的做法是给「出现次数数组」排序。但由于可能有O(N)个不同的出现次数(其中Ⅳ为原数组长度)，故总的算法复杂度会达到O(N log N)，不满足题目的要求。在这里，我们可以利用堆的思想:建立一个小顶堆，然后遍历「出现次数数组」∶ 如果堆的元素个数小于k，就可以直接插入堆中。如果堆的元素个数等于k，则检查堆顶与当前出现次数的大小。如果堆顶更大，说明至少有k个数字的出现次数比当前值大，故舍弃当前值;否则，就弹出堆顶，并将当前值插入堆中。遍历完成后，堆中的元素就代表了「出现次数数组」中前k大的值。

5 我的答案

队列：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int num:nums){
            map.put(num,map.getOrDefault(num,0)+1);
        }
        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
            @Override
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

        for(Integer key:map.keySet()){
            if(queue.size()==k){
                int count = map.get(queue.peek());
                if(count<map.get(key)){
                    queue.poll();
                    queue.add(key);
                }
            }else{
                queue.add(key);
            }
        }
        int[] res = new int[k];
        for(int i=0;i<k;i++){
            res[i] = queue.poll();
        }
        return res;
    }
}

堆：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> occurrences = new HashMap<Integer, Integer>();
        for (int num : nums) {
            occurrences.put(num, occurrences.getOrDefault(num, 0) + 1);
        }

        // int[] 的第一个元素代表数组的值，第二个元素代表了该值出现的次数
        PriorityQueue<int[]> queue = new PriorityQueue<int[]>(new Comparator<int[]>() {
            public int compare(int[] m, int[] n) {
                return m[1] - n[1];
            }
        });
        for (Map.Entry<Integer, Integer> entry : occurrences.entrySet()) {
            int num = entry.getKey(), count = entry.getValue();
            if (queue.size() == k) {
                if (queue.peek()[1] < count) {
                    queue.poll();
                    queue.offer(new int[]{num, count});
                }
            } else {
                queue.offer(new int[]{num, count});
            }
        }
        int[] ret = new int[k];
        for (int i = 0; i < k; ++i) {
            ret[i] = queue.poll()[0];
        }
        return ret;
    }
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2022-07-25，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

编程算法

登录后参与评论

0 条评论

热度