首页 > 代码库 > 【LEETCODE】:Sort Characters By Frequency
【LEETCODE】:Sort Characters By Frequency
题目链接:https://leetcode.com/problems/sort-characters-by-frequency
题目简述:将给定的字符串按照出现频率由高到低排序后返回
思路:将输入的字符串按照字符与出现次数映射到一个map中,然后对map进行排序后输出
第一次代码如下:
class cisort{ public: bool operator() (pair<char,int> p1,pair<char,int> p2) const{ return p1.second > p2.second; } }; class Solution { public: string frequencySort(string s) { string ret; map<char,int,cisort> countmap; // 获取映射关系 for(size_t i = 0;i < s.length();++i){ if(countmap.find(s.at(i)) != countmap.end()){ countmap[s.at(i)]++; } else{ countmap[s.at(i)] = 1; } } while(countmap.size() != 0){ map<char,int>::iterator it = countmap.begin(); ret += string(it->first,it->second); countmap.erase(it->first); } return ret; } };
编译错误,因为map是按照key进行排序的,这里的cisort企图使用仿函数使map按照value进行排序。编译时会由于map<char,int,cisort> countmap中的第三个参数报错——无法将char转换为pair<char,int>,因为C++企图将map的key类型char传递给cisort的operator(),因此报错——map默认使用key进行排序。
在此可以采取迂回的方式,比如将map中的pair放入vector中,使vector按照cisort排序,最终代码如下:
class cisort { public: bool operator() (const pair<char, int> p1, const pair<char, int> p2) const { return p1.second > p2.second; } }; class Solution { public: string frequencySort(string s) { string ret; map<char, int> countmap; // 获取映射关系 for (size_t i = 0; i < s.length(); ++i) { (countmap.find(s.at(i)) != countmap.end()) ? (countmap[s.at(i)]++) : (countmap[s.at(i)] = 1); } vector<pair<char, int> > sortcount(countmap.begin(), countmap.end()); sort(sortcount.begin(), sortcount.end(), cisort()); for (vector<pair<char, int> >::iterator it = sortcount.begin(); it != sortcount.end(); ++it) { ret += string(it->second, it->first); } return ret; } };
【LEETCODE】:Sort Characters By Frequency
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。