【LeetCode刷题笔记：451.根据字符出现频率排序】

71 阅读 0 评论 47 点赞

我是靠谱客的博主默默汽车，最近开发中收集的这篇文章主要介绍【LeetCode刷题笔记：451.根据字符出现频率排序】，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目:
在这里插入图片描述
今天这题的思路算是比较简单的，遍历一遍得到每个字符出现的数量，然后根据数量大小排序直接替换string字符即可。

但是，写这题的时候没注意看下面的测试用例还有大写字母，所以一开始就按照全小写字母的方式去建立了一个26X2的二维数组，用于统计数量导致出错。

优化方法也很简单，既然多了大写字母，那么为了避免额外的一些开销，我们这里还是使用哈希表比较好。因此，思路就变为：

我们使用哈希表去存储每一个字符出现的数量。
然后将数量和对应字符使用一个Pair暂存到一起，让其可以插入Vector中使用Sort（）函数进行排序。排序完成之后，重新构造字符串或者替换原本字符的思路都可以。

C++代码附带测试：

#include<iostream>
#include<vector>
#include<algorithm>
#include<unordered_map>

using namespace std;

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> mp;
        int length = s.length();
        for (auto &ch : s) {
            mp[ch]++;
        }
        vector<pair<char, int>> vec;
        for (auto &it : mp) {
            vec.emplace_back(it);
        }
        sort(vec.begin(), vec.end(), [](const pair<char, int> &a, const pair<char, int> &b) {
            return a.second > b.second;
        });
        string ret;
        for (auto& temp : vec) {
        	char ch = temp.first;
        	int num = temp.second;
            for (int i = 0; i < num; i++) {
                ret.push_back(ch);
            }
        }
        return ret;
    }
};


int main()
{
	string s = "tree";
	Solution solution;
	cout<<solution.frequencySort(s)<<endl;
}