451. Sort Characters By Frequency
451. 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.
方法1: sort
Complexity
Time complexity: O(n log n)
Space complexity: O(26)
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> hash;
for (char c: s) hash[c]++;
auto cmp = [&](const char & a, const char & b) {
if (hash[a] == hash[b]) return a < b;
return hash[a] > hash[b];
};
sort(s.begin(), s.end(), cmp);
return s;
}
};
方法1: hash + heap
思路:
这里用到的本质算法是counting sort,主要因为必须保证相同字符连续输出。定义cmp 的方法stable不stable都无法解决这个问题。(可以解决!在词频一致的情况下按照lexicographic order比较,上面的方法) 。
Complexity
Time complexity: O(n),下面证明heapify是o(n), tighter bound than O(n log n)
Space complexity: O(n)
class Solution {
public:
string frequencySort(string s) {
string res;
unordered_map<char, int> hash;
priority_queue<pair<int, char>> pq;
for (char c: s) hash[c]++;
for (auto item: hash) pq.push({item.second, item.first});
while (!pq.empty()) {
auto top = pq.top();
pq.pop();
res += string(top.first, top.second);
}
return res;
}
};
上一篇: 浅谈Servlet的生命周期
下一篇: 浅谈jsp与servlet
推荐阅读
-
451. Sort Characters By Frequency
-
排序LeetCode 451 Sort Characters By Frequency
-
【Leetcode】451. 根据出现的频率对字符排序(Sort Characters By Frequency)
-
LeetCode 451. 根据字符出现频率排序(Sort Characters By Frequency)
-
LeetCode | 0451. Sort Characters By Frequency根据字符出现频率排序【Python】
-
LeetCode 451. Sort Characters By Frequency 按照字符频率排序(Java实现)
-
LeetCode 22 May, Sort Characters By Frequency, 按字符出现频率排序字符串
-
Leetcode 451.根据字符出现频率排序(Sort Characters By Frequency)
-
451 Sort Characters By Frequency 根据字符出现频率排序
-
Sort Characters By Frequency 根据字符出现频率排序