451. Sort Characters By Frequency

題目描述

題目連結：Sort Characters By Frequency

題目要求給定一個字串，要求將字串中的字母按照出現頻率進行排序，頻率高的字母排在前面，頻率相同的字母順序可以隨意

題目理解

題目的核心是統計每個字母在字串中出現的頻率，並根據頻率將字母排序。我們可以利用hash table來統計頻率，利用優先佇列來進行排序

約束條件

1. 給定的字串長度範圍為 1 <= s.length <= 5 * 10^5
2. 字串由 ASCII 字符組成

解題思路

Priority Queue

1. 統計字母頻率：使用 unordered_map 統計每個字母的出現次數
2. 排序：使用 priority queue 來根據字母頻率進行排序
3. 構建結果：從優先佇列中依次取出字母，根據其頻率將其追加到結果字串中

class Solution {
public:
    string frequencySort(string s) {
        unordered_map<char, int> counter;
        priority_queue<pair<int, char>> pq;
        
        for (const char ch : s) {
            counter[ch] += 1;
        }

        for (auto [ch, count] : counter) {
            pq.push({count, ch});
        }

        string ans = "";
        while (!pq.empty()) {
            ans += string(pq.top().first, pq.top().second);
            pq.pop();
        }
        
        return ans;
    }
};

• 時間複雜度：O(n log n)
• 空間複雜度：O(n)

Bucket sort

1. 統計字母頻率：使用 unordered_map 統計每個字母的出現次數
2. 桶排序：根據頻率將字母放入對應的桶中
3. 構建結果：從桶中取出字母，按頻率從高到低構建結果字串

class Solution {
public:
    string frequencySort(string s) {
        const int n = s.size();
        unordered_map<char, int> counter;
        vector<string> bucket(n + 1, "");
        for (const char ch : s) {
            counter[ch] += 1;
        }

        for (auto [ch, count] : counter) {
            bucket[count].append(count, ch);
        }

        string ans = "";
        for (int i = n; i >= 0; i -= 1) {
            if (!bucket[i].empty()) {
                ans += bucket[i];
            }
        }
        return ans;
    }
};

• 時間複雜度：O(n)
• 空間複雜度：O(n)