[LeetCode] Sort Characters By Frequency 根据字符出现频率排序

发布时间:2017-3-30 16:45:53 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"[LeetCode] Sort Characters By Frequency 根据字符出现频率排序 ",主要涉及到[LeetCode] Sort Characters By Frequency 根据字符出现频率排序 方面的内容,对于[LeetCode] Sort Characters By Frequency 根据字符出现频率排序 感兴趣的同学可以参考一下。

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

Example 1:

Input:
"tree"

Output:
"eert"

Explanation:
'e' appears twice while 'r' and 't' both appear once.
So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.

Example 2:

Input:
"cccaaa"

Output:
"cccaaa"

Explanation:
Both 'c' and 'a' appear three times, so "aaaccc" is also a valid answer.
Note that "cacaca" is incorrect, as the same characters must be together.

Example 3:

Input:
"Aabb"

Output:
"bbAa"

Explanation:
"bbaA" is also a valid answer, but "Aabb" is incorrect.
Note that 'A' and 'a' are treated as two different characters.

这道题让我们给一个字符串按照字符出现的频率来排序,那么毫无疑问肯定要先统计出每个字符出现的个数,那么之后怎么做呢?我们可以利用优先队列的自动排序的特点,把个数和字符组成pair放到优先队列里排好序后,再取出来组成结果res即可,参见代码如下:

解法一:

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;
    }
};

我们也可以使用STL自带的sort来做,关键就在于重写comparator,由于需要使用外部变量,记得中括号中放入&,然后我们将频率大的返回,注意一定还要处理频率相等的情况,要不然两个频率相等的字符可能穿插着出现在结果res中,这样是不对的。参见代码如下:

解法二:

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> m;
        for (char c : s) ++m[c];
        sort(s.begin(), s.end(), [&](char& a, char& b){
            return m[a] > m[b] || (m[a] == m[b] && a < b);
        });
        return s;
    }
};

我们也可以不使用优先队列,而是建立一个字符串数组,因为某个字符的出现次数不可能超过s的长度,所以我们将每个字符根据其出现次数放入数组中的对应位置,那么最后我们只要从后往前遍历数组所有位置,将不为空的位置的字符串加入结果res中即可,参见代码如下:

解法三:

class Solution {
public:
    string frequencySort(string s) {
        string res = "";
        vector<string> v(s.size() + 1, "");
        unordered_map<char, int> m;
        for (char c : s) ++m[c];
        for (auto& a : m) {
            v[a.second].append(a.second, a.first);
        }
        for (int i = s.size(); i > 0; --i) {
            if (!v[i].empty()) {
                res.append(v[i]);
            }
        }
        return res;
    }
};

参考资料:

https://discuss.leetcode.com/topic/66045/c-o-n-solution-without-sort

https://discuss.leetcode.com/topic/65914/concise-c-solution-using-stl-sort

上一篇:巨化集团公司——业务流程管理平台
下一篇:jquery.each()

相关文章

相关评论

本站评论功能暂时取消,后续此功能例行通知。

一、不得利用本站危害国家安全、泄露国家秘密,不得侵犯国家社会集体的和公民的合法权益,不得利用本站制作、复制和传播不法有害信息!

二、互相尊重,对自己的言论和行为负责。

好贷网好贷款