347 O(nlog(n-k))

来源:6-7 优先队列相关的算法问题 Top K Frequent Elements

易小鸭

2019-08-05

老师,第347题按照你的提示,我提交了如下代码,但好像代码没有变得更简洁,请问如何更改进呢?

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;
        //(元素,频率)
        unordered_map<int,int> freq;
        unordered_map<int,int>::iterator iter;
        for(int num:nums)
            freq[num]++;
        int n = freq.size();
        //(频率,元素)
        priority_queue<pair<int,int>> pq;
        for(iter=freq.begin();iter!=freq.end();iter++){
            if(pq.size() == n-k) {
                if(n-k!=0 && iter->second < pq.top().first) {
                    pq.pop();
                    pq.push(make_pair(iter->second,iter->first));
                }
            }
            else
                pq.push(make_pair(iter->second,iter->first));
        }
        while(!pq.empty()) {
            freq.erase(pq.top().second);
            pq.pop();
        }
        for (auto k:freq)
            res.push_back(k.first);
        return res;
    }
};
写回答

1回答

liuyubobobo

2019-08-06

你的这个代码是可以AC的。


抱歉,我没有理解你说的“更简洁”是什么意思?

0
3
易小鸭
回复
liuyubobobo
嗯嗯,确实是用最小堆的时候老师说了写起来很繁琐。。。。。谢谢bobo老师啦~
2019-08-07
共3条回复

玩转算法面试-- Leetcode真题分门别类讲解

课程配套大量BAT面试真题,高频算法题解析,强化训练

7408 学习 · 1150 问题

查看课程