LeetCode 347前K个高频元素

• 题目简述：给定一个非空的整数数组，返回其中出现频率前 k 高的元素。注意：题目数据保证答案唯一，可以按任意顺序返回答案。

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

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

• 思路：小根堆+哈希表

  使用哈希表统计每个数字出现的个数，然后维护一个大小为k的小根堆依次将哈希表中的元素和频率加入，如果小根堆中元素个数超过了k，就将堆顶出现频率较小的元素弹出，直到将哈希表元素遍历完，留在小根堆中的元素就是出现频率前k高的元素。

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> hash;
        for(auto x : nums) hash[x]++;//hash中<元素，频率>
        //priority_queue<int, vector<int>, greater<int>> q; //定义小根堆
        priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>> > q;
        int i = 0;
        //小根堆优先以pair中的第一个元素为准排序
        for(auto &it : hash)
        {
            if(i < k)
            {
                i ++;
                q.push(make_pair(it.second,it.first));//pair中<频率，元素>
            }
            else
            {
                if(it.second > q.top().first)
                {
                    q.pop();
                    q.push(make_pair(it.second,it.first));
                }
            }
        }
        vector<int> res;
        for(int i = 0 ; i < k ; i ++)
        {
            res.push_back( q.top().second );
            q.pop();
        }

        return res;
    }
};
           

• 计数排序+哈希表
  • 首先利用哈希表建立元素和频率的映射关系，所有数出现的次数频率都在 1到 n 之间
  • 再利用输入数组大小的新数组

    vec

    统计每个频率出现了多少次，数组下标表示频率，如示例1中，共

    6

    个数，

    1

    出现

    3

    次，

    2

    出现

    2

    次，

    3

    出现

    1

    次，那么

    vec=[0, 1, 1, 1, 0, 0, 0]

  • vec

    相当于按照频率进行了排序，从频率最高的开始统计一下出现次数为

    t

    次的元素各有多少个
  • 利用计数排序判断出现前

    k

    多次的数字最少出现多少次，求出下界
  • 再遍历一次哈希表将所有出现次数大于等于这个下界的元素加入答案

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> hash;//hash中<元素，频率>
        for(auto x : nums) hash[x]++;
        int n = nums.size();
        vector<int> vec(n+1, 0);
        for(auto &it : hash) vec[it.second] ++;//统计每个频率出现次数
        //for(auto y : vec) cout << y <<" ";//查看vec数组
        int cnt = 0, t = n; 
        while(t--)
        {
            cnt += vec[t];
            if(cnt >= k) break;
        }
        //while(cnt < k) cnt += vec[t--];//类似写法,仅需修改if(it.second > t)
        vector<int> res;
        for(auto &it : hash)      
            if(it.second >= t) res.push_back(it.first);
        return res;
    }
};