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

思路

1、使用优先级队列，构建大根堆或者小根堆
2、使用map<string, int>记录每一个string出现的次数

代码

class Solution {
public:
    /**
     * return topK string
     * @param strings string字符串vector strings
     * @param k int整型 the k
     * @return string字符串vector<vector<>>
     */

    /*
    // 小根堆，头部是小的
    struct cmp{
      bool operator()(const pair<string, int>& p1, const pair<string, int>& p2 ){
          return(p1.second>p2.second || (p1.second==p2.second && p1.first<p2.first));
      }  
    };

    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        vector<vector<string>> res;
        unordered_map<string, int> umap;
        for(auto ele:strings){
            umap[ele]+=1;
        }

        // 优先级队列表示堆
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
        for(const auto& ele:umap){
            if(pq.size()<k){
                pq.emplace(pair<string, int>(ele.first, ele.second));
            }
            else if( ele.second>pq.top().second || (ele.second==pq.top().second && ele.first<pq.top().first) ){
                pq.pop();
                pq.emplace(pair<string, int>(ele.first, ele.second));
            }
        }
        while(!pq.empty()){
            res.push_back(vector<string> {pq.top().first, to_string(pq.top().second)});
            pq.pop();
        }

        reverse(res.begin(), res.end());

        return res;


    }
    */


    // 大根堆，头部是大的，
    struct cmp{
      bool operator()(const pair<string, int>& p1, const pair<string, int>& p2 ){
          return(p1.second<p2.second || (p1.second==p2.second && p1.first>p2.first));
      }  
    };

    vector<vector<string> > topKstrings(vector<string>& strings, int k) {
        // write code here
        vector<vector<string>> res;
        unordered_map<string, int> umap;
        for(auto ele:strings){
            umap[ele]+=1;
        }

        // 优先级队列表示堆，将map中的所有元素放进去
        priority_queue<pair<string, int>, vector<pair<string, int>>, cmp> pq;
        for(const auto& ele:umap){
            pq.emplace(pair<string, int>(ele.first, ele.second));
        }

        int i = 0;
        while(!pq.empty() && i<k){
            res.push_back(vector<string> {pq.top().first, to_string(pq.top().second)});
            pq.pop();
            i++;
        }

//         reverse(res.begin(), res.end());

        return res;


    }
};