[数据结构与算法]LeetCode_347. 前K个高频元素(优先队列(小顶堆)/哈希表)

思路(优先队列)

1. 首先将值和其出现的次数存储到一个哈希表中形成映射关系；
2. 然后我们创建一个优先队列，存储的元素就是哈希表中的键值对，我们根据值(出现次数)，由小到大排列，(实现原理就是小顶堆)；
3. 遍历哈希表的元素，将元素放入优先队列中，放入的过程中队列会自动根据出现次数由小到大将元素存入；我们在存入过程中就可以根据题目中的k控制放入元素的数量，题目要求前K个高频元素，所以我们就可以保持优先队列中有K个元素，当队列中元素超过K时，就讲队头出现次数较小的元素弹出，依次加入和弹出
4. 最后遍历队列，将哈希表的键存到最终的结果集中即可

实现代码(java)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();
        // 将值和出现的数量存储到 哈希表 中
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 得到小顶堆的优先队列，队头存储的是出现次数较小的元素
        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o1.getValue() - o2.getValue());

        // 遍历哈希表中的各个元素
        final Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
        for (Map.Entry<Integer, Integer> entry : entries) {
            queue.offer(entry);
            // 如果队列长度大于k 则将队头较小的元素弹出，这样队列中存储的就是最后k个较大的元素
            if (queue.size() > k) {
                queue.poll();
            }
        }

        // 遍历队列，得到哈希表中的键，即为前K个高频元素
        int[] res = new int[k];
        for (int i = k - 1; i >= 0; i--) {
            res[i] = queue.poll().getKey();
        }

        return res;
    }
}