LeetCode思考

前K个高频元素

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

1. 思路

首先需要统计数组的频率，为了可以方便、高效地查找元素对应的频率，我们使用一个哈希表（unordered_map）来统计；然后对频率排序，找出出现频率最高的K个元素即可。
那么问题来了，如何对频率排序以及排序之后如何把频率对应到元素上来？

1.1 代码

解决了1中的问题，unordered_map如何排序。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> m;
        for(auto i:nums){
            if(m.count(i))
            m[i]++;
            else
            m[i]=1;
        }
        vector<pair<int,int>> v;
        for(auto i:m){
            v.push_back(i);
        }
        sort(v.begin(),v.end(),[](auto &p1,auto &p2){return p1.second>p2.second;});
        vector<int>re;
        for(int i=0;i<k;i++)
        {
            re.push_back(v[i].first);
        }
        return re;
    }
};

执行用时：12 ms, 在所有 C++ 提交中击败了83.42%的用户
内存消耗：13.3 MB, 在所有 C++ 提交中击败了36.24%的用户
通过测试用例：21 / 21

使用了自带的sort函数来排序，在时间复杂度上表现很好。
但是如果不直接使用sort函数呢？

2. 题解

仍使用unordered_map来统计关键字频率，但是使用堆排序来求得频率最大的K个元素。注：小根堆。
堆用priority_queue来维护，priority_queue相关在priority_queue这篇博客。

2.1 代码

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        //统计频率
        unordered_map<int,int> m;
        for(auto &i:nums){
            if(m.count(i))
            m[i]++;
            else
            m[i]=1;
        }
        //做一个仿函数
        class myCompare{
            public:
            bool operator()(pair<int,int>&a,pair<int,int>&b){
                return a.second>b.second;
            }
        };
        //堆排序
        //定义优先队列
        priority_queue<pair<int,int>,vector<pair<int,int>>,myCompare> p;
        //维护小根堆
        for(auto &i:m){
            p.push(i);
            if(p.size()>k)
            p.pop();
        }
        //取结果
        vector<int> re;
        while(!p.empty()){
            re.push_back(p.top().first);
            p.pop();
        }
        return re;
    }
};

执行用时：16 ms, 在所有 C++ 提交中击败了47.10%的用户
内存消耗：13.1 MB, 在所有 C++ 提交中击败了94.16%的用户
通过测试用例：21 / 21

版权声明： 如无特别声明，本文版权归 月梦の技术博客 所有，转载请注明本文链接。

（采用 CC BY-NC-SA 4.0 许可协议进行授权）

本文标题：《 HOT100 347前k个高频元素 》

本文链接：https://ymiir.asia/leetcode/HOT100-347.html

本文最后一次更新为 天前，文章中的某些内容可能已过时！

目录