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

1. 所有的看注释

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) {
        // write code here

        if(!strings.size() || strings.size()<k) return {};

        map<string, int> m;

        vector<string> ss;
        vector<vector<string> > res;
        //排序
        sort(strings.begin(),strings.end());


        for(int i =0; i< strings.size();i++){
            m[strings[i]]++;
        }
        //用匿名函数（对于堆而言，数字比骄是相反的，但是字符序时不变的）
        auto cmp = []( pair<string,int> p1, pair<string,int> p2){
            if(p2.second!=p1.second){
                return p1.second > p2.second;//最小堆
            }
            return p1.first < p2.first;


        };//自定义匿名比较器

        //注意声明
        priority_queue<pair<string,int>,vector<pair<string,int>>, decltype(cmp)>  pq(cmp);

        int i = 0;
        for(auto it=m.begin(); it!= m.end();it++){

             pq.emplace(*it);//map 和 字典是可以互插的。

            if (pq.size() > k)// 这是一个小技巧，当大于一的时候，弹走那些尾端最小的就行
                               //然后每次插入的时候都从头插入就行
                pq.pop();

        }

        while(!pq.empty()){
            pair<string, int> p = pq.top();
            pq.pop();
            //从头插，就可以间接逆序。
            res.insert(res.begin(), vector<string>{p.first, to_string(p.second)} );
        }


        return res;


    }
};