每日一道算法题--leetcode 347--前K个高频元素--python&C++

【题目描述】

!!!求top K问题的常规思路：维护一个大小为k的堆，求最大的k个数用小根堆，求最小的k个数用大根堆。

以求最大的k个数为例，迭代比对，每个元素与小根堆的堆顶元素top比较大小，如果大于top则将堆顶替换掉，更新所维护的堆。最终将堆中元素返回即为top k大的元素。这道题，求topk高频元素，相当于求词频top k的所有元素。利用Python中的字典或者c++中的hashmap，求出元素与词频的对应关系即可。

python:
class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        import heapq
        #heapq默认构成小根堆，item的话按照先第一个元素再第二个元素的判断顺序
        dic={}
        for num in nums:
            dic[num]=dic.get(num,0)+1
        p=[]
        for item in dic.items():
            if len(p)<k:
                heapq.heappush(p,(item[1],item[0]))
            else:
                if p[0][0]<item[1]:
                    heapq.heappop(p)
                    heapq.heappush(p,(item[1],item[0]))
        return [i[1] for i in p]

C++:优先队列本质是一个堆实现的,对于基础类型默认是大顶堆，所以通过将词频取负的方式，实现topk中词频小的位于堆顶，以便于替换。

//priority_queue push:插入元素到队尾 (并排序,形成大根堆)
//pop:弹出队头元素
//top:访问队头元素

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> re;
        unordered_map<int,int> mp;
        priority_queue<pair<int,int>> pq;
        for(auto i:nums) mp[i]++;
        for(auto p:mp){
            pq.push(pair<int,int>(-p.second,p.first) );
            if (pq.size()>k) pq.pop();
        }
        while(k--){
            re.push_back(pq.top().second);
            pq.pop();
        }
        return re;    
    }
};

关于C++中优先队列详情可以参考这篇