题目：top-k-frequent-elements

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。

你可以按 任意顺序 返回答案。

示例 1：

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

示例 2：

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

解题思路

1. 先遍历数组，用 hashMap 存频率（key：整数， value：出现次数）
2. 用优先队列（最小堆），排序规则：按出现频率 map.get() 的值排序
3. 将 HashMap 的所有 key 都存入最小堆，只保留前 k 个
4. 将堆数组化，返回数组

Java 实现

import java.util.*;

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 存频率（key：整数， value：出现次数）
        Map<Integer, Integer> frequencyMap = new HashMap<>();
        for (int num : nums) {
            frequencyMap.put(num, frequencyMap.getOrDefault(num, 0) + 1);
        }

        // 2. 创建小顶堆，堆里存放的是数组元素
        // 比较器 (a, b) -> frequencyMap.get(a) - frequencyMap.get(b) 保证频率小的在堆顶
        PriorityQueue<Integer> pq = new PriorityQueue<>(
            (a, b) -> frequencyMap.get(a) - frequencyMap.get(b)
        );

        // 3. 遍历哈希表，维护大小为 k 的小顶堆
        for (int key : frequencyMap.keySet()) {
            pq.add(key); 
            // 如果堆的大小超过了 k，就弹出堆顶元素（即当前堆里频率最低的元素）
            // 这样保证堆里始终保留的是目前为止频率最高的前 k 个元素
            if (pq.size() > k) {
                pq.poll();
            }
        }

        // 4. 取出堆中剩下的 k 个元素放入结果数组
        int[] result = new int[k];
        for (int i = 0; i < k; i++) {
            result[i] = pq.poll();
        }
        
        return result;
    }
}