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

小顶堆
保持堆的大小不超过k+1即可；
时间复杂度方面，本题应该漏了字符串的长度应该是一个常数，否则复杂度不是

class Solution {
public:
     struct Node{
         string s;
         int cnt;
         Node(string _s, int _cnt):s(_s), cnt(_cnt){}
         bool operator < (const Node& other) const{
             if(cnt == other.cnt) return s < other.s;
             else return cnt > other.cnt;
         }
     };
    /**
     * 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> ump;
        for(string s:strings) ump[s] ++;
        priority_queue<Node> pq; //小顶堆
        for(pair<string,int> p:ump){
            pq.push(Node(p.first, p.second));
            if(pq.size() > k) pq.pop();
        }
        vector<vector<string>> res;
        while(!pq.empty()){
            Node node = pq.top(); pq.pop();
            res.push_back({node.s, to_string(node.cnt)});
        }
        reverse(res.begin(), res.end());
        return res;
    }
};