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

#define PSI pair<string,int>
class mycompare{
public:
    //小顶堆：使用的是greater比较方法，也就是谁的优先级大，就返回谁
    //那么这里首先频率大的就是greater,其次字典序小的就是greater。
    //所以我们这里使用的compare，就是根据这个greater思想来写的
    bool operator()(const PSI &lhs,const PSI &rhs){
        if(lhs.second > rhs.second)return true;
        if(lhs.second == rhs.second)return lhs.first < rhs.first;
        return false;
    }
};
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> counts;
        for(auto &element : strings){
            ++counts[element];
        }
        priority_queue<PSI,vector<PSI>,mycompare> pq;
        for(auto &element : counts){
            if(pq.size() < k)pq.push(element);
            else if(mycompare()(element,pq.top())){
                pq.pop();pq.push(element);
            }
        }
        vector<vector<string>> ans(k);
        int index = 0;
        while(!pq.empty()){
            auto current = pq.top();pq.pop();
            ans[--k] = {current.first,to_string(current.second)};
        }
        return ans;
    }
};