347 O(nlog(n-k)) 的疑惑

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

面包猎人

2020-03-07

老师，按照您的提示我实现了维护n-k个元素的大根堆的方法。leetcode题目给的原始测试用例nums = [1,1,1,2,2,3], k = 2通过了，但是提交leecode之后卡在了测试用例nums = [1], k = 1上，自己调了好一会儿也不得其解。可以请您指导一下我的代码嘛？辛苦您啦！
错误信息：Line 784: Char 17: runtime error: reference binding to null pointer of type 'const struct pair' (stl_iterator.h)

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int,int> record;  //(元素，频率)
        //遍历数组，录入频率
        for(int i = 0; i < nums.size(); i++){
            record[nums[i]]++;
        }
        int n = record.size();

        //扫描record。维护当前出现频率最少的n-k个元素
        //最大堆。如果当前元素的频率小于优先队列中最大频率元素的频率，则替换
        //优先队列中，按频率排序，所以数据对是(频率，元素)形式
        priority_queue< pair<int,int> > pq;
        for(auto iter = record.begin(); iter != record.end(); iter++){
            if((n - k) == pq.size()){ //队列已满
                if(iter->second < pq.top().first){
                    pq.pop();
                    pq.push(make_pair(iter->second,iter->first));
                }
            }
            else{
                pq.push(make_pair(iter->second,iter->first));
            }
        }

        vector<int> result;
        while(!pq.empty()){
            record.erase(pq.top().second);
            pq.pop();
        }
        for(auto iter : record){
            result.push_back(iter.first);
        }
        return result;
    }
};

写回答

1回答

liuyubobobo

2020-03-07

已采纳

对这个测试用例，n == k，所以在初始 pq 为空的时候，if((n - k) == pq.size()) 成立（为 0），但是 pq 为空，不能访问 pq.top()，也不能做 pq.pop()

我的修改：

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        
        unordered_map<int,int> record;  //(元素，频率)
        //遍历数组，录入频率
        for(int i = 0; i < nums.size(); i++){
            record[nums[i]]++;
        }
        int n = record.size();
        
        vector<int> result;
        if(n != k){ // 如果 n == k，根据题意，直接统计 record 中的元素就好了
            
            //扫描record。维护当前出现频率最少的n-k个元素
            //最大堆。如果当前元素的频率小于优先队列中最大频率元素的频率，则替换
            //优先队列中，按频率排序，所以数据对是(频率，元素)形式
            priority_queue< pair<int,int> > pq;
            for(auto iter = record.begin(); iter != record.end(); iter++){
                if((n - k) == (int)pq.size()){ //队列已满
                    if(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()){
                record.erase(pq.top().second);
                pq.pop();
            }
        }
        
        for(auto iter : record){
            result.push_back(iter.first);
        }
        return result;
    }
};

继续加油！：）

面包猎人

懂啦懂啦，谢谢老师☺️

2020-03-09

共1条回复

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

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

7408 学习 · 1150 问题

查看课程

相似问题

347 O(nlog(n-k))

回答 1