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

#include <functional>
#include <queue>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
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) {
        function<bool(pair<string, int> &, pair<string, int> &)> cmp = [](pair<string, int> &a, pair<string, int> &b) -> bool {
            return a.second < b.second || a.second == b.second && a.first > b.first;
        };
        priority_queue<pair<string, int>, vector<pair<string, int> >, decltype(cmp)> pq(cmp);
        unordered_map<string, int> hash;
        for (auto &s: strings) {
            ++hash[s];
        }
        for (auto &item: hash) {
            pq.push(item);
        }
        vector<vector<string> > res;
        for (int i = 0; i < k; ++i) {
            if (pq.empty()) {
                return {};
            }
            res.push_back({pq.top().first, to_string(pq.top().second)});
            pq.pop();
        }
        return res;
    }
};

思路：topK一般用优先队列/堆。

先统计出字符串与其频数，然后通过自定义排序的优先队列解决即可。