347 O(nlog(n-k))

Question

老师，第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;
    }
};

Answer 1

liuyubobobo 2019-08-06 00:16:11

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

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

• 提问者 易小鸭 #1

  抱歉说得不太清楚。。是因为听到老师在课上说“用O(nlog(n-k))实现的会比O(nlogk)实现的过程简洁许多”，虽然我这个可以AC，但好像没有简洁许多。。所以觉得自己是不是哪里做得不对呢？

• liuyubobobo 回复 提问者 易小鸭 #2

  额。。。抱歉，我都已经忘了我留过这个思考题了。关键是，我有点儿想不起来我讲课的时候为什么这么说了。。。对于topk问题，求前k大元素，使用最小堆是一个标准解法。但如果n - k << k 的话，使用最大堆存储前 n-k 个最小元素，空间上更优。我可能那时候想的是，此时直接使用C++的priority_queue就好了，默认就是最大堆，不需要进行别的定义了。。。：）

• 提问者 易小鸭 回复 liuyubobobo #3

  嗯嗯，确实是用最小堆的时候老师说了写起来很繁琐。。。。。谢谢bobo老师啦~