首页 > 代码库 > 【LEETCODE】:Sort Characters By Frequency

【LEETCODE】:Sort Characters By Frequency

2024-09-15 03:01:37   218人阅读

题目链接：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


联系
我们