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

struct cmp{
    bool operator() (const pair<string, int>& a, const pair<string, int>& b){
        return a.second > b.second || ((a.second == b.second) && a.first < b.first);
    }
};

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        unordered_map<string, int> tb;
        for(int i=0; i<strings.size(); i++){
            tb[strings[i]] += 1;
        }
        
        priority_queue<pair<string, int>, vector<pair<string,int>>, cmp> pq;
        
        int i=0;
        for(auto it = tb.begin(); it != tb.end(); it++, i++){
            if(i < k){
                pair<string, int> a = {it->first, it->second};
                pq.push(a);
            }
            else{
                auto a = pq.top();
                if(a.second < it->second || (a.second == it->second && a.first > it->first)){
                    pq.pop();
                    pair<string, int> a = {it->first, it->second};
                    pq.push(a);
                }
            }
        }
        
        vector<vector<string>> res;
        while(!pq.empty()){
            auto a = pq.top();
            res.push_back({a.first, to_string(a.second)});
            pq.pop();
        }
        reverse(res.begin(), res.end());
        
        return res;
    }
};