题解 | 字符串出现次数的TopK问题

#include <queue>  //string、vector、algorithm
#include <utility>  //pair需要
class Solution {
public:
    /**
    记录次数，放入小根堆，维护堆size不超过K, 放入二维数组中需要反转，注意在堆中字典序大的应该放在后面
     */
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        if( k==0 ){
            return {};
        }

        unordered_map<string, int> mp={};
        for(const string& s: strings){
            mp[s]++;
        }

        auto cmp = [](const pair<string, int>& a, const pair<string, int>& b){
            if(a.second == b.second){
                return a.first < b.first;
            }
            return a.second > b.second;};  //设置优先队列的排序规则，a是放在后面

        priority_queue< pair<string, int>, vector< pair<string, int> >, decltype(cmp) > pq(cmp);  
        //需要使用decltype()（类型推导关键字，编译时获取类型）处理lambda函数,函数类型，pq(比较函数)

        for(auto& p:mp){
            if(pq.size() <k){
                pq.push( p );
            }else if( !cmp(pq.top(), p) ){  //直接用排序函数，直接利用true的判断
                pq.pop();
                pq.push(p);
            }
        }

        vector< vector<string> > ans={};
        while(pq.size()>0){
            ans.push_back( {pq.top().first, to_string(pq.top().second)} );
            pq.pop();
        }

        reverse(ans.begin(), ans.end());

        return ans;
    }
};