Last Updated on 2022-12-03 by Clay
題目
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them.
Example 1:
Input: s = "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: s = "cccaaa" Output: "aaaccc" Explanation: Both 'c' and 'a' appear three times, so both "cccaaa" and "aaaccc" are valid answers. Note that "cacaca" is incorrect, as the same characters must be together.
Example 3:
Input: s = "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.
題目會給定一組字串，字串中可能包含大小寫的英文字母。而我們要按照各字母出現的頻率，依照最常出現的字母到最少出現字母的順序，重新排列字串。
解題思路
這題使用 C++ 中的 priority_queue 能很輕易地解出來，只需要在佇列中同時儲存出現頻率及字母即可。
以下是一段 C++ 範例程式碼，因為我不確定 Python 是否有同樣的資料結構實作，所以今次就只有拿 C++ 來寫題目。
C++ 範例程式碼
class Solution {
public:
string frequencySort(string s) {
// Create a map to store the frequency of each character in the string
std::unordered_map<char, int> freq;
for (const auto& c : s) {
freq[c]++;
}
// Create a max-heap to store the characters in the string, sorted by their frequency
std::priority_queue<std::pair<int, char>, std::vector<std::pair<int, char>>, std::less<std::pair<int, char>>> heap;
for (const auto& [c, f] : freq) {
heap.push({f, c});
}
// Build the result string by popping the characters from the max-heap
std::string result;
while (!heap.empty()) {
const auto& [f, c] = heap.top();
result.append(f, c);
heap.pop();
}
return result;
}
};