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 日 星期五