LeetCode-347:Top K Frequent Elements (前K个频率最高的元素)

时间:2022-09-18 19:16:45

题目:

Given a non-empty array of integers, return the k most frequent elements.

例子:

Example:

Given [1,1,1,2,2,3] and k = 2, return [1,2].

Note:
* You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
* Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.

问题解析:

给定一个非空的整数数组,返回前K个频率最高的元素。

链接:

思路标签

HashMappriority_queue(最大堆)桶排序

解答:

1.hashmap + 优先级队列(最大堆)的解法,时间复杂度O(nlog(n-k))

  • 利用hashmap统计各个元素出现的个数,构成(key,value)对;
  • 利用优先级队列(最大堆)来存储(value,key)对;
  • 因为需要返回top K个高频元素,所以堆的大小保持在map.size()-(k+1)即可;
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for(int i=0; i)
            count[num]++;

        vector<int> res;
        priority_queue<pair<int, int> > pq;
        for(auto it = count.begin(); it != count.end(); ++it){
            pq.push(make_pair(it->second, it->first));
            if(pq.size() > count.size()-k){
                res.push_back(pq.top().second);
                pq.pop();
            }
        }
        return res;
    }
};

2.hashmap + 桶排序的解法,时间复杂度O(n

  • 利用hashmap统计各个元素出现的个数,构成(key,value)对;
  • 利用桶来存储(value,key)对,(利用vector实现即可);
  • 桶中存储的是出现对应个数的元素,从后向前将存在元素的桶中的元素压入返回vector,不存在的则由程序直接跳过;
  • 注意vector从0开始,要生成nums.size()+1大小的桶,来避免0的情况;
class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for(auto num : nums)
            count[num]++;

        vector<vector<int> > buckets(nums.size()+1);
        for(auto p : count)
            buckets[p.second].push_back(p.first);

        vector<int> res;
        for(int i=buckets.size()-1; i>=0 && res.size()<k; --i){
            for(int b : buckets[i]){
                res.push_back(b);
                if(res.size() == k)
                    return res;
            }
        }

        return res;
    }
};