451. 根据字符出现频率排序 -自定义排序

46 阅读 0 评论 31 点赞

我是靠谱客的博主痴情日记本，最近开发中收集的这篇文章主要介绍451. 根据字符出现频率排序 -自定义排序，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

451. 根据字符出现频率排序
题目：
　　给定一个字符串，请将字符串里的字符按照出现的频率降序排列。
　　
示例1：

输入:
"tree"

输出:
"eert"

解释:
'e'出现两次，'r'和't'都只出现一次。
因此'e'必须出现在'r'和't'之前。此外，"eetr"也是一个有效的答案。

思路：
　　　这个题目一看感觉非常简单，但是处理的时候会麻烦点。直观上就是用哈希表来计算频率，根据频率排序，但是计算频率简单，从频域中进行排序又要做些手段了。为了方便排序，我们把哈希表的元素提取auto取出来存入一个vector里面，vector里面用pair来承载哈希表。然后可以通过pair的first和second来实现对哈希表元素的查找。在vector中重新排序哈希表元素，按照频率最高的原则排序，然后再遍历vector，将结果按照频率次数拼接再string中

class Solution {
public:
    string frequencySort(string s) {
        int n=s.size();
        //记录频率
        unordered_map<char,int>map;
        for(int i=0;i<n;i++)
            map[s[i]]++;
        //提取频率分量到数组
        vector<pair<char,int>>pdd;
        for(auto & m:map)
            pdd.push_back(m);
        //剖析频率分量 冒泡排序
        for(int i=0; i<pdd.size()-1;i++){
            for(int j=0;j<pdd.size()-1-i;j++){
                if(pdd[j].second>pdd[j+1].second){
                    pair<char,int> temp;
                    temp=pdd[j];
                    pdd[j]=pdd[j+1];
                    pdd[j+1]=temp;
                }
            }         
        }
        reverse(pdd.begin(),pdd.end());
        string res;
        for(int i=0;i<pdd.size();i++)
            for(int j=0;j<pdd[i].second;j++)
                res+=pdd[i].first;
        
        return res;        
    }
};

为了避免reverse的排序时间，对冒泡做了改进。逆序冒泡：

class Solution {
public:
    string frequencySort(string s) {
        int n=s.size();
        //记录频率
        unordered_map<char,int>map;
        for(int i=0;i<n;i++)
            map[s[i]]++;
        //提取频率分量到数组
        vector<pair<char,int>>pdd;
        for(auto & m:map)
            pdd.push_back(m);
        //剖析频率分量 冒泡排序
        for(int i=0; i<pdd.size()-1;i++){
            for(int j=pdd.size()-1;j>i;j--){
                if(pdd[j].second>pdd[j-1].second){
                    pair<char,int> temp;
                    temp=pdd[j];
                    pdd[j]=pdd[j-1];
                    pdd[j-1]=temp;
                }
            }         
        }
        string res;
        for(int i=0;i<pdd.size();i++)
            for(int j=0;j<pdd[i].second;j++)
                res+=pdd[i].first;
        
        return res;        
    }
};

如果是自定义排序的话：

class Solution {
public:
    static bool cmp(const pair<int,int> &a,const pair<int,int>&b){ //const 和& 可以同时不用
        return a.second > b.second ; //a是新来的，符合条件的新的跳到前面
                                     
}
        

    string frequencySort(string s) {
        int n=s.size();
        //记录频率
        unordered_map<char,int>map;
        for(int i=0;i<n;i++)
            map[s[i]]++;
        //提取频率分量到数组
        vector<pair<char,int>>pdd;
        for(auto & m:map)
            pdd.push_back(m);
        //剖析频率分量 sort排序
        sort(pdd.begin(),pdd.end(),cmp);
        string res;
        for(int i=0;i<pdd.size();i++)
            for(int j=0;j<pdd[i].second;j++)
                res+=pdd[i].first;
         
        return res;        
    }
};

桶排序的话：
　　由于每个字符在字符串中出现的频率存在上限，因此可以使用桶排序的思想，根据出现次数生成排序后的字符串。具体做法如下：
　　遍历字符串，统计每个字符出现的频率，同时记录最高频率；
　　创建桶，存储从 11 到 textit{maxFreq}maxFreq 的每个出现频率的字符；
　　按照出现频率从大到小的顺序遍历桶，对于每个出现频率，获得对应的字符，然后将每个字符按照出现频率拼接到排序后的字符串。
　　总结就是桶排序用次数下里面东西是什么。实现了对哈希表的反转！！！　这个以后可以用。哈希表是东西多少次

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int maxFreq = 0;
        int length = s.size();
        for (auto &ch : s) {
            maxFreq = max(maxFreq, ++mp[ch]);
        }
        vector<string> buckets(maxFreq + 1);
        for (auto &[ch, num] : mp) {
           // buckets[num].push_back(ch); //某个数量的字母不止一个 所以用string string可以用push back
            buckets[num]+=ch; 
        }
        string ret;
        for (int i = maxFreq; i > 0; i--) {
            string &bucket = buckets[i];
            for (char &ch : bucket) {
                for (int k = 0; k < i; k++) {
                    ret.push_back(ch);
                }
            }
        }
        return ret;
    }
};