给定String类型的数组strArr，再给定整数k，请严格按照排名顺序打印 出次数前k名的字符串。
[要求]
如果strArr长度为N，时间复杂度请达到O(N \log K)O(NlogK)
输出K行，每行有一个字符串和一个整数（字符串表示）。 你需要按照出现出现次数由大到小输出，若出现次数相同时字符串字典序较小的优先输出
示例1
复制
["1","2","3","4"],2复制
[["1","1"],["2","1"]]
基本思路：
采取map<string,int> 遍历一遍数组 记录下每种字符串出现的次数
priority_queue构建一个小根堆（因为求解的是最大的k个） 默认是大根堆
首先实现自定的比较器 cmp实现一个operator() 函数
struct cmp { bool operator()(const pair<string,int>& a,const pair<string,int>& b) { if(a.second==b.second) { return a.first<b.first; } return a.second>b.second; } };C++中容器类 priority_queue创建方式：
priority_queue<int> q;//默认大根堆 priority_queue<int,vector<int>,greator<int>> q;//定义内置类型 的小根堆 priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> q;//定义pair类型的小根堆其中cmp是即为我们实现的比较器，通常规则：
小根堆 实现 > 比较
大根堆 实现 < 比较
先将K个数据放入优先队列，构建出一个小根堆。而后每一个数据，与小根堆堆顶（在k个中最小）比较，若新来的数据更大，那么替换出堆顶。
易错点：
本文要求，最终结果若字符串出现数目相同，那么优先输出字典序小的，因此需要始终确保堆顶的字典序最大（若其与第二小的数量相同），这需要比较器处理num想等的情况。
struct cmp { bool operator()(const pair<string,int>& a,const pair<string,int>& b) { if(a.second==b.second) { return a.first<b.first; } return a.second>b.second; } }; 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 map<string,int> mp; for(int i=0;i<strings.size();i++) { mp[strings[i]]++; } priority_queue<pair<string,int>,vector<pair<string,int>>,cmp> q;//小项堆 int count=0; for(map<string,int>::iterator it=mp.begin();it!=mp.end();it++) { pair<string,int> one(it->first,it->second); if(count<k) { q.push(one); count++; } else { //大于k的时候 每一个新来的与小根堆 堆顶 做一个比较 if(q.top().second<one.second) { q.pop(); //若新来的更大 那么置换出堆顶 q.push(one); } else if(q.top().second==one.second) { if(q.top().first>one.first) //数字相等情况下 字典序小的进入 { q.pop(); q.push(one); } } } } vector<vector<string>> ans; while(q.empty()==false) { ans.push_back({q.top().first,to_string(q.top().second)}); q.pop(); } reverse(ans.begin(),ans.end()); return ans; } };
