LeetCode451. Sort Characters By Frequency（模拟）

LeetCode451. Sort Characters By Frequency（模拟）

• Medium
• Accepted：81,281
• Submissions：148,685

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.

链接

https://leetcode.com/problems/sort-characters-by-frequency/

题意

给定一个字符串，按照字符出现的频率从大到到小排序。相同字符相邻，频率相同时不同字符顺序可以不同，区分大小写。

题解

• 对字符按照出现次数用sort进行排序，时间复杂度$O(nlogn)$
• 对字符进行“计数排序”，灵活使用vector，将出现次数相同的字符放到一起，再从后往前遍历

代码

• Runtime: 48 ms, faster than 30.00% of C++ online submissions for Sort Characters By Frequency.
• Memory Usage: 10.5 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.
• 话说直接写cmp函数会报错（已发现错误：reference to non-static member function must be called）

class Solution {
public:
//    int cnt[256] = {0};
//
//    bool cmp(char a, char b)
//    {
//        return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
//    }

    string frequencySort(string s) {
        int n = s.length();
        int cnt[256] = {0};
        for (int i = 0; i < n; ++i)
            cnt[s[i]]++;
        // sort(s.begin(), s.end(), cmp); // error
        sort(s.begin(), s.end(), [&](char a, char b) // 高级写法
        {
             return cnt[a] > cnt[b] || (cnt[a] == cnt[b] && a < b);
        });
        return s;
    }
};

• Runtime: 28 ms, faster than 42.31% of C++ online submissions for Sort Characters By Frequency.
• Memory Usage: 18.6 MB, less than 100.00% of C++ online submissions for Sort Characters By Frequency.

class Solution {
public:
    string frequencySort(string s) {
        int n = s.length();
        unordered_map <char, int> umap;
        vector <string> vt(n + 1, "");
        string ans;
        for (int i = 0; i < n; ++i) // 统计字符出现次数
            umap[s[i]]++;
        unordered_map <char, int> ::iterator it;
        for (it = umap.begin(); it != umap.end(); ++it) // 次数相同的放到一起
            vt[it->second].append(it->second, it->first);
        for (int i = n; i > 0; --i) // 从后往前遍历
        {
            if (!vt[i].empty())
                ans.append(vt[i]);
        }
        return ans;
    }
};

The end.
2019年2月15日 星期五