題目網址：https://leetcode.cn/problems/sort-characters-by-frequency/

題意：給一 string s, 根據每個 char 出現的頻率對其進行降序排列。

返回已排序過的 string, 若有多個答案, 則返回其中任意一個。

Solution：

想法：利用 Heap

  • 計算 s 中每個元素的出現頻率
  • 將 {char, cnt} push 到 max heap 中
  • 不斷取出 top 直到 heap 為空, s.append(cnt, char) 代表 s 一次新增 cnt 個 char
class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        priority_queue<pair<int, char>> q; // max heap

        for (const auto& ch : s) {
            ++freq[ch];
        }

        for (const auto& [ch, cnt] : freq) {
            q.emplace(cnt, ch);
        }

        s = "";
        while (!q.empty()) {
            const auto [cnt, ch] = q.top();
            s.append(cnt, ch);
            q.pop();
        }

        return s;
    }
};
  • time：$O(n)$ ➔ $O(n) + O(26 \cdot log(n))$
    • $O(n)$：第一個 for loop 和 while loop 的 s.append()
    • $O(26 \cdot log(n))$：第二個 for loop 和 while loop, 因為 char 最多 26 種, 因此 q 的元素不超過 26 個
  • space：$O(1)$ ➔ 因為 freq 和 q 最多 26 個元素, 且 s 為 input string, 故只需常數空間