LeetCode347——前K个高频元素

Yuansj0206 / 2023-09-06 / 原文

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

示例 1:

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

示例 2:

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

提示：

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

这是一道经典的topK问题，去找前K个最大值，可以维护一个小顶堆，然后通过遍历后面的元素，若找到比堆顶大的元素，则插入这个元素，若小顶堆的长度已经超过K，则抛出堆顶元素，重新构建小顶堆，这样，遍历完剩余元素后，小顶堆中存在的K个元素就是topK元素。

在Java中可以使用优先队列PriorityQueue去构建小顶堆，将优先队列升序排列即为小顶堆。

这个题还考察了hashMap统计元素个数以及hashMap的遍历方式，使用entrySet()结构进行遍历，将Map.Entry<>结构存储到优先队列中

class Solution {
    public int[] topKFrequent(int[] nums, int k) {

        //topK问题  通常思路为 使用hashmap去统计每个元素出现的次数，然后利用优先队列的性质（小根堆）去维护topK元素,优先队列升序排序即为小顶堆，降序排序即为大顶堆

        Map<Integer,Integer> map = new HashMap<>();
        List<Integer> list = new ArrayList<>();
        for(int num : nums)
        {
            if(!map.containsKey(num))
            {
                map.put(num,1);
            }
            else
            {
                map.put(num,map.get(num) + 1);
            }
        }
        Set<Map.Entry<Integer,Integer>> set = map.entrySet();
        System.out.println(map.entrySet());

        PriorityQueue<Map.Entry<Integer,Integer>> queue = new PriorityQueue<>((o1,o2) -> o1.getValue()-o2.getValue());
        for(Map.Entry<Integer,Integer> entry : set)
        {
            queue.offer(entry);
            if(queue.size() > k)
            {
                queue.poll();
            }
        }
        int[] result = new int[k];
        for(int i = 0;i<k;i++)
        {
            result[i] = queue.poll().getKey();
            System.out.println(result[i]);
        } 

        return result;
    }
}