347. 前 K 个高频元素

解法一

先统计出现频率，然后维护一个大小为k的优先队列，保留频率前k大的元素。

import java.util.Comparator;
import java.util.HashMap;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // key: 元素值
        // value: 出现频率
        Map<Integer, Integer> count = new HashMap<>();
        for (int i : nums) {
            count.put(i, count.getOrDefault(i, 0) + 1);
        }
        System.out.println(count);
        Comparator<int[]> queueComparator = new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        };
        // 优先队列, 保留前k个的元素
        Queue<int[]> queue = new PriorityQueue<>(queueComparator);
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int key = entry.getKey();
            int value = entry.getValue();
            if (queue.size() < k) {
                queue.offer(new int[] { key, value });
            } else if (queue.peek()[1] < value) {
                queue.poll();
                queue.offer(new int[] { key, value });
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; ++i) {
            ans[i] = queue.poll()[0];
        }
        return ans;
    }
}