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

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    struct cmp {  // 次数不同，次数少的在堆顶；次数相同，则字典序大的在堆顶
        bool operator() (pair<string, int> &a, pair<string, int> &b){
            //出现次数较高 或 出现次数相同字典序小的优先级高（堆顶的元素优先级最低）
            return a.second > b.second || (a.second == b.second && a.first < b.first);
        }
    };

    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        vector<vector<string> > ans;
        unordered_map<string, int> mp;
        for (string & s:strings) mp[s]++;
        priority_queue<pair<string, int>, vector<pair<string, int> >, cmp> pq; //自定义优先队列
        for (auto it = mp.begin(); it != mp.end(); it++) { // 遍历无序map
            if (pq.size() < k)  // 当堆元素数小于k直接入堆
                pq.emplace(pair<string, int>{it->first, it->second});
            else if (it->second > pq.top().second || (it->second == pq.top().second && it->first < pq.top().first)) {
                pq.pop();
                pq.emplace(pair<string, int>{it->first, it->second});
            }
        }
        while (!pq.empty()) {  // 前k个字符次数从小到大
            ans.emplace_back(vector<string> {pq.top().first, to_string(pq.top().second)});
            pq.pop();
        }
        reverse(ans.begin(), ans.end()); // 翻转，前k个字符次数从大到小
        return ans;  // 返回结果
    }
};