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

#include <queue>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */
    struct Compare {
        bool operator()(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;
        }
    };
    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        if (strings.size() == 0) {
            return {};
        }

        unordered_map<string, int> countMap;
        for (auto& str : strings) {
            countMap[str]++;
        }

        priority_queue<pair<string, int>, vector<pair<string, int>>, Compare> prq;
        vector<vector<string>> result;

        for (auto& [str, count] : countMap) {
            if (prq.size() < k) {
                prq.push({str, count});
            } else {
                pair<string, int> curr{str, count};
                if (count > prq.top().second 
                || (count == prq.top().second && str < prq.top().first)) {
                    prq.pop();
                    prq.push(curr);
                }
            }
        }

        while (!prq.empty()) {
            vector<string> vec;
            vec.push_back(prq.top().first);
            vec.push_back(to_string(prq.top().second));
            result.push_back(vec);
            prq.pop();
        }
        
        reverse(result.begin(), result.end());

        return result;
    }
};