451. 根据字符出现频率排序 MediumLeetcode笔记目录一、题目描述二、解题过程三、总结

107 阅读 0 评论 71 点赞

我是靠谱客的博主靓丽钢铁侠，这篇文章主要介绍451. 根据字符出现频率排序 MediumLeetcode笔记目录一、题目描述二、解题过程三、总结，现在分享给大家，希望可以做个参考。

Leetcode笔记目录

451. 根据字符出现频率排序 Medium

Leetcode笔记目录
一、题目描述
二、解题过程
- 1.思想
- 2.代码
三、总结

一、题目描述

给定一个字符串，请将字符串里的字符（区分大小写）按照出现的频率降序排列。

示例1：

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

示例2：

输入: “cccaaa”
输出: “cccaaa”
解释: 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。注意"cacaca"是不正确的，因为相同的字母必须放在一起。

二、解题过程

1.思想

TOPK问题，与Leetcode347几乎一样，可以采用同样的方法，只是输出不一样，本次采用桶排序(计数排序)，适合TOPK中数组长度较小的时刻：

先用map统计每个字符出现的频率；
然后桶排序，此时也是hash，使用二维数组方便操作，即A[频率]={所有此频率的字符}。

2.代码

最初版本：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
string frequencySort(string s) {
        string result;
        int count=0;
        unordered_map<char,int> hash;
        for(int i=0;i<s.size();i++){
            hash[s[i]]++;
            count = max(count,hash[s[i]]);
        }
        vector<vector<char>> mid(count+1);  //错误1 必须加范围 不然可能越界
        for(auto it:hash) mid[it.second].push_back(it.first);
        for(int i=count;i>=1;i--){
            for(int l=0;l<mid[i].size();l++)
                for(int j=0;j<i;j++)
                    result += mid[i][l];
        }
        return result;
    }