[Vssue]0347.前K个高频元素.md

[youngyangyang04]

https://programmercarl.com/0347.%E5%89%8DK%E4%B8%AA%E9%AB%98%E9%A2%91%E5%85%83%E7%B4%A0.html

[Du1in9]

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 1. 统计每个元素的频率
        Map<Integer, Integer> map = new HashMap<>();
        for (int n : nums)
            map.put(n, map.getOrDefault(n, 0) + 1);
        // 2. 保存出现频率前 k 高的元素
        PriorityQueue<Integer> minHeap = new PriorityQueue<>((a, b) -> map.get(a) - map.get(b));
        for (int key : map.keySet()) {
            minHeap.offer(key);
            if (minHeap.size() > k) 
                minHeap.poll();
        }
        // 3. 从堆中提取最上面的 k 个元素
        int[] res = new int[k];
        int i = 0;
        while (!minHeap.isEmpty())
            res[i++] = minHeap.poll();
        return res;
    }
}

[MusherM]

先map再sort倒是能过

[JIE-yx]

@MusherM

先map再sort倒是能过

时间复杂度怎么样？sort会全排序，但是题目只需要top K的排序。理论上sort结果提供的信息是有部分冗余的，超过了题目所需的信息