思路：

题目的主要信息：

需要统计字符串出现的频率
最大复杂度为O(nlgk)
选出频率前K，相同频率算字典序最小

方法一：排序法

使用先统计次数，再排序，再找出前k的策略，但是不符合题目要求！！！！

不符合规定

复杂度分析：

时间复杂度：O(nlgn)，排序算法最快O(nlgn)，遍历前k个
空间复杂度：O(1)，无额外空间

方法二：哈希表+小顶堆

拥有关联的一组数据快速访问，我们想到了哈希表，快速找到topK我们想到了小顶堆：当超过k时，与堆顶比较，若堆顶较小，则将堆顶pop出，加入新的元素。

具体做法：

使用map当哈希表，记录字符串与出现次数，做到快速访问。遍历哈希表，将其加入小顶堆中，如果超过了k则用上述策略更新堆。（当然堆的比较策略需要重载：出现频率更高的或者相同时字典序更小的）最后输出因为是小顶堆，所以需要逆序输出。图片说明

class Solution {
public:
    struct cmp {  //重载比较规则
    bool operator() (pair<string, int> p1, 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) {
        vector<vector<string> > res;
        unordered_map<string, int> mp; //统计字符串出现次数
        priority_queue<pair<string, int>, vector<pair<string, int> >, cmp> pq; //重载比较的小顶堆
        for(int i = 0; i < strings.size(); i++)  //次数加入哈希表
            mp[strings[i]]++;
        for(auto iter = mp.begin(); iter != mp.end(); iter++) { 
            if(pq.size() < k) //用k限制堆大小
                pq.push(pair<string, int> {iter->first, iter->second}); 
            //当超过k，需要判断是否将最小的取出加入新的
            else if(iter->second > pq.top().second || (iter->second == pq.top().second && iter->first < pq.top().first)) { 
                pq.pop();
                pq.push(pair<string, int> {iter->first, iter->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; 
    }
};

复杂度分析：

时间复杂度：O(nlgk)，维护堆每次为lgk，最多为n次
空间复杂度：O(n)，哈希表最大为n

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

思路：