题目描述
给定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 heremap<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;}
};