Leetcode451 Sort Characters By Frequency

90 阅读 0 评论 60 点赞

我是靠谱客的博主孝顺小蝴蝶，这篇文章主要介绍Leetcode451 Sort Characters By Frequency，现在分享给大家，希望可以做个参考。

Given a string, sort it in decreasing order based on the frequency of characters.

Example 1:

复制代码

1
2
3
4
5
6
7
8
Input:
"tree"

Output:
"eert"

本题就是要把字符串里的数字按频率降序输出。注意题目中说，频率相同的字母顺序随便排都是合理答案。

一看次数，直接想到哈希表，所以我用了map，发现其实好多map不知道的基础知识，有时间了在补一补吧。先说思路

map建立字符和出现次数的关系，map<char,int>.然后在根据value对map进行降序排列就可以了。难点就是如何降序排列。

可以先看一下这篇博客https://blog.csdn.net/qq_26399665/article/details/52969352。基本思想就是将map放进vector中，在对vector进行排序。

排完之后直接输出就可以，但是注意的是，输出的时候遇到每个字符多次的要输出多次该字符，就是在要嵌套一层循环，否则就只会输出一个该字符。

AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    static bool cmp(const pair<char,int> &p1,const pair<char,int> &p2) 
    {
	    return p1.second>p2.second;
    }
    string frequencySort(string s) {
        map<char,int> m;
        for(int i=0;i<s.length();i++){
            m[s[i]]++;
        }
        vector<pair<char,int>> arr;
        for (map<char,int>::iterator it=m.begin();it!=m.end();++it){
   	        arr.push_back(make_pair(it->first,it->second));
        }
        sort(arr.begin(),arr.end(),cmp);
        int i=0;
        for(vector<pair<char,int>>::iterator it=arr.begin();it!=arr.end();++it){
            for(int j=0;j<it->second;j++){
                s[i++]=it->first;   
            }
        }
        return s;
    }
};

今天看了另一个方法，思路一样，但是代码很简单，用了自动排序的数据结构priority_queue ，优先队列。

定义了priority_queue<pair<int,int>>,优先队列会自动排序，默认是降序，优先级大的在前，符合这道题的要求。如果数据类型是pair的话，则会按pair 的first元素排序，first相同在按second排序。

所以生成pair的时候将频率当first元素。

AC代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    string frequencySort(string s) {
        string res = "";
        priority_queue<pair<int, char>> q;
        unordered_map<char, int> m;
        for (char c : s) ++m[c];
        for (auto a : m) q.push({a.second, a.first});
        while (!q.empty()) {
            auto t = q.top(); q.pop();
            res.append(t.first, t.second);
        }
        return res;
    }
};