题解 | #字符串出现次数的TopK问题#
字符串出现次数的TopK问题
http://www.nowcoder.com/practice/fd711bdfa0e840b381d7e1b82183b3ee
这个题还挺有意思的，很多人都会想到先用字典计数，然后利用对计数排序来做。
我也是这个思路，不过我更倾向于插入排序，效率更改，内存更低。
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;
vector<pair<string, int>> list;
vector<vector<string> > res;
for(string s : strings){
mp[s]++;
}
for (auto it = mp.begin(); it != mp.end(); ++it)
{
pair<string, int> val = {it->first,it->second};
insertTopK(list, k,val);
}
for(int i=0;i<k;i++){
string count = to_string(list[i].second);
vector<string> p = {list[i].first,count};
res.push_back(p);
}
return res;
}
void insertTopK(vector<pair<string, int>> &list,int k,pair<string, int> &val){
bool flag = false;
for(int i=0;i<list.size();i++){
if(list[i].second < val.second){
list.insert(list.begin()+i, val);
flag = true;
break;
}
}
if(!flag){
list.insert(list.end(), val);
}
if(list.size() > k){
list.erase(list.end());
}
}
};
