提问者:小点点

优先队列自定义比较器


下面是从数组中获取前K个频繁元素的代码。代码是正确的,但我对比较器在这里做什么感到困惑。为什么是"p1.秒

class Solution {
struct compare {
    bool operator() (pair<int, int>p1, pair<int, int>p2) {
        return p1.second > p2.second;
    }
};

public:向量topK频繁(向量

    int n = nums.size();
    
    unordered_map<int, int>m;
    for (int i = 0; i < n; i++) {
        m[nums[i]]++;
    }
    
    priority_queue<pair<int, int>, vector<pair<int, int>>, compare>pq;
    for (auto it = m.begin(); it != m.end(); it++) {
        pq.push(make_pair(it->first, it->second));
        if (pq.size() > k)
            pq.pop();
    }
    
    vector<int>v;
    while (!pq.empty()) {
        pair<int, int>p = pq.top();
        v.push_back(p.first);
        pq.pop();
    }
    
    return v;
**}

};**


共3个答案

匿名用户

默认情况下,std::priority_queue使用std::less比较器。在这种情况下,pop()删除最大的元素。

但是,在您的情况下,您希望将k最大的元素保留在队列中,而pop()最小的元素(丢弃它)。为此,您需要颠倒比较的意义。

匿名用户

优先级队列所做的是在容器上构建一个堆,容器的尾部是堆的顶部,

匿名用户

当我们想要以自定义的方式构建堆时,比较器函数作为参数传递。堆的一个节点存储两个值,元素及其频率。由于您使用的是对