C++标准库priority_queue自定义排序

2021/7/5 1:22:06

本文主要是介绍C++标准库priority_queue自定义排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

  • 重写仿函数
class Solution {
public:

    struct compare {
        bool operator ()(const pair<int,int> &a, const pair<int,int> &b) {
            return a.second>b.second;
        }
    };

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;        
        unordered_map<int, int> countMap;

        for (auto &item:nums) {
            countMap[item]++;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, compare> q;

        for (auto &[num, count]:countMap) {
            if (q.size()==k) {
                if (count>q.top().second) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }

        while (!q.empty()) {
            res.push_back(q.top().first);
            q.pop();
        }

        return res;
    }
};
  • 自定义函数
class Solution {
public:
    static bool cmp(const pair<int,int> &a, const pair<int,int> &b)
    {
        return a.second>b.second;
    }

    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<int> res;        
        unordered_map<int, int> countMap;

        for (auto &item:nums) {
            countMap[item]++;
        }

        priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(&cmp)> q(cmp);

        for (auto &[num, count]:countMap) {
            if (q.size()==k) {
                if (count>q.top().second) {
                    q.pop();
                    q.emplace(num, count);
                }
            } else {
                q.emplace(num, count);
            }
        }

        while (!q.empty()) {
            res.push_back(q.top().first);
            q.pop();
        }

        return res;
    }
};
  • 重载运算符
    注意priority_queue默认使用less的比较函数,所以此处重载<运算符,如果使用greater的比较函数,则需重载>运算符。
class Solution {
public:
    struct Status {
        int val;
        int x;
        int y;

        bool operator < (const struct Status &rhs) const {
            return val > rhs.val;
        }
    };

    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int row=matrix.size();
        int col=matrix[0].size();
        priority_queue<Status> q;

        for (int i=0;i<row;i++) {
            q.push({matrix[i][0], i, 0});
        }

        for (int i=0;i<k-1;i++) {
            auto f=q.top();
            q.pop();
            if (f.y<col-1) {
                q.push({matrix[f.x][f.y+1], f.x, f.y+1});
            }
        }

        return q.top().val;
    }
};


这篇关于C++标准库priority_queue自定义排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程