【leetcode】451. Sort Characters By Frequency

　　　Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string. Return the sorted string. If there are multiple answers, return any of them.

　　考察了map的创建，map转存到vector，函数参数传递进去自定义排序（关系仿函数）这题还是比较需要基本功的。

class Solution {

public:

    // 仿函数

    typedef pair<char,int> PAIR;

    struct CmpByValue{

        bool operator()(const PAIR& lhs,const PAIR& rhs){

            return lhs.second>=rhs.second;//

        }

    };

    string frequencySort(string s) {

        //按照频率统计字符串 第一件事情就是要提取出字符 计算频率

        //哈希表进行排序？

        // 处理步骤 先用map村数值 然后转存到vector 指定仿函数修改排序规则

        map<char,int> dp;

        for(char ss:s){

            if(dp.find(ss)==dp.end()){

                dp[ss]=1;

            }

            else{

                dp[ss]++;

            }

        }

        // 将map元素转存到vector中

        vector<PAIR> dp2(dp.begin(),dp.end());

        // 对vector排序

        sort(dp2.begin(),dp2.end(),CmpByValue());

        //根据排序后的元素拼接新的字符串

        string res="";

        for(auto dd:dp2){

            string tmp(dd.second,dd.first);

            res+=tmp;

        }

        return res;

    }

};

　　为了避免map中key键值重复的问题利用优先队列（默认大顶堆）重建以出现次数为key的优先队列，减少时间复杂度。

class Solution {

public:

    string frequencySort(string s) {

        //按照频率统计字符串 第一件事情就是要提取出字符 计算频率

        //哈希表进行排序？

        // 处理步骤 先用map村数值 然后转存到vector 指定仿函数修改排序规则

        map<char,int> dp;

        for(char ss:s){

            dp[ss]++;

        }

        //利用优先队列 大顶堆直接做

        priority_queue<pair<int,char>> q;//这样避免了key不能重复的问题

        string res="";

        for(auto dd:dp){

            q.push({dd.second,dd.first});

        }

        while(!q.empty()){

            auto c=q.top();

            string tmp(c.first,c.second);

            res+=tmp;

            q.pop();

        }

        return res;

    }

};

巴特西

【leetcode】451. Sort Characters By Frequency

最新文章

热门文章