Leetcode451:根据字符出现频率排序——桶排序
目录
题目
https://leetcode-cn.com/problems/sort-characters-by-frequency/
题解
思路
用一个哈希map先统计每个字符出现的次数,然后再排序,最后拼接字符串。排序的方法多种多样,因为字符是有限的(26个小写,26个大写,0-9数字),所以使用桶排序是最好的选择。
桶排序
假设你对2,5,3三个数字排序,最大的数字是5,所以你拿来五个桶,从头到尾遍历这三个数字。然后把数字放在相同标号的桶里,比如第一个数字是2,就把它放在标号为2的桶里,5就放在标号为5的桶,3就放在标号为3的桶里。最后再把1号到5号桶遍历,空的跳过,就完成了排序。典型的空间换时间,当已知不会消耗很大的空间时,桶排序无非是效率最高的。
具体做法如下:
-
遍历字符串,统计每个字符出现的频率,同时记录最高频率maxFreq;
-
创建桶,存储从 11 到 maxFreq 的每个出现频率的字符;
-
按照出现频率从大到小的顺序遍历桶,对于每个出现频率,获得对应的字符,然后将每个字符按照出现频率拼接到排序后的字符串。
代码:
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> mp;
int maxFreq = 0;
int length = s.size();
for (auto &ch : s) {
maxFreq = max(maxFreq, ++mp[ch]);
}
vector<string> buckets(maxFreq + 1);
for (auto &[ch, num] : mp) {
buckets[num].push_back(ch);
}
string ret;
for (int i = maxFreq; i > 0; i--) {
string &bucket = buckets[i];
for (auto &ch : bucket) {
for (int k = 0; k < i; k++) {
ret.push_back(ch);
}
}
}
return ret;
}
};
作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/sort-characters-by-frequency/solution/gen-ju-zi-fu-chu-xian-pin-lu-pai-xu-by-l-zmvy/ 来源:力扣(LeetCode) 著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。
时间复杂度:O*(n+*k),其中 n 是字符串 s 的长度,k 是字符串 s 包含的不同字符的个数。
空间复杂度:O*(n+*k)