题目描述

前 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 <= 10<sup>5</sup>
• k 的取值范围是 [1, 数组中不相同的元素的个数]
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的

进阶： 你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。

解题思路

先用哈希表记录每个元素出现的次数。
然后你可以直接按照出现次序排序，但是这样排序最快要O(nlogn),可以进一步优化，用优先队列来做：
先开一个小根堆，让上面计算出的元素和频次依次入队。如果队列中元素数量小于k个，新元素直接入队，如果已有k个，则让队头元素频次（队中最小）和新元素的出现频次比较，如果新元素的出现频次小于队头元素频次，说明队列中k个元素频次均大于当前新元素，所以舍弃该新元素。反之如果新元素频次大于队头元素频次，则队头出队，新元素插入。最终队列中的k个元素就是出现频次最高的k个元素了。

代码

vector<int> topKFrequent(vector<int>& nums, int k) {
    unordered_map<int, int> dp;
    for(auto num : nums){
        dp[num]++;
    }
    //自定义小根堆比较器
    auto cmp = [](auto p1, auto p2)->bool{return p1.second > p2.second;};
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp) > pque(cmp);
    for(auto pa : dp){
        if(pque.size() < k){
            pque.push(pa);
        }
        else{
            if(pque.top().second < pa.second){
                pque.pop();
                pque.push(pa);
            }
        }
    }
    vector<int> topk;
    while(pque.empty() == false){
        topk.push_back(pque.top().first);
        pque.pop();
    }
    return topk;
}

时间复杂度：$O(nlogk)$
空间复杂度：$O(n)$