347. 前 K 个高频元素

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

示例 1:

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

示例 2:

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

提示：

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

解法

1. 借助Map转List排序

public int[] topKFrequent(int[] nums, int k) {
    // mapVal<元素, 出现次数>
    Map<Integer, Integer> mapVal = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        mapVal.put(nums[i], mapVal.getOrDefault(nums[i], 0) + 1);
    }

    // mapCnt<出现次数, List<元素>>
    Map<Integer, List<Integer>> mapCnt = new HashMap<>();
    for (Map.Entry<Integer, Integer> entry : mapVal.entrySet()) {
        List<Integer> sameCntVals = mapCnt.get(entry.getValue());
        if (sameCntVals == null) {
            sameCntVals = new ArrayList<>();
            mapCnt.put(entry.getValue(), sameCntVals);
        }
        sameCntVals.add(entry.getKey());
    }

    // mapCnt 转 list
    List<Pair> list = new ArrayList<>();
    for (Map.Entry<Integer, List<Integer>> entry : mapCnt.entrySet()) {
        list.add(new Pair(entry.getKey(), entry.getValue()));
    }
    
    // 按出现次数排序
    list.sort((a, b) -> (b.cnt - a.cnt));

    // 取前 k 个元素
    List<Integer> result = new ArrayList<>();
    for (int i = 0; i < list.size() && k > 0; i++) {
        for (Integer val : list.get(i).vals) {
            result.add(val);
            k--;
        }
    }
    
    // list 转数组
    int[] res = new int[result.size()];
    for (int i = 0; i < result.size(); i++) {
        res[i] = result.get(i);
    }
    return res;
}

static class Pair{
    int cnt;
    List<Integer> vals;
    public Pair(int cnt, List<Integer> vals) {
        this.cnt = cnt;
        this.vals = vals;
    }
}

2. 优先级队列

先遍历统计每个值的频率，使用map存储。然后再使用优先级队列取出前k个即可。

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
    }

    PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1, o2) -> o2.getValue() - o1.getValue());
    for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
        queue.offer(entry);
    }
    int[] result = new int[k];
    int n = 0;
    while (!queue.isEmpty() && n < k){
        result[n++] = queue.poll().getKey();
    }
    return result;
}