4 min read leetcode

451. Sort Characters By Frequency

451. Sort Characters By Frequency
Photo by Markus Spiske / Unsplash

題目連結：Sort Characters By Frequency

題目描述

給定一個字串，請根據字母出現的頻率將其排序，頻率高的字母排在前面。如果頻率相同，字母的順序可以隨意。

限制條件

  • 1 <= s.length <= 5 * 10^5
  • 字串由 ASCII 字元組成

解題思路

此題要求我們根據字母出現的頻率對字串進行排序。我們需要統計每個字母的出現次數，然後根據頻率進行排序。

有兩種有效的解法：

方法一：優先佇列（Priority Queue）

  1. 統計字母頻率：使用 unordered_map（雜湊表）來統計每個字母的出現次數。
  2. 建立優先佇列：使用 priority_queue，根據頻率從高到低排序字母。
  3. 構建結果字串：從優先佇列中依次取出字母，根據其頻率將字母添加到結果字串中。

詳細解釋

  • 統計字母頻率：
    • 使用 unordered_map<char, int>，鍵為字母，值為出現次數。
    • 遍歷字串，對每個字母累加計數。
  • 建立優先佇列：
    • 使用 priority_queue<pair<int, char>>，根據頻率進行排序。
    • 頻率高的字母會被優先取出。
  • 構建結果字串：
    • 從優先佇列中取出一個元素，取得字母及其頻率。
    • 使用 string::append 函數，將該字母重複 count 次添加到結果字串。

程式碼

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 k)
    • n 是字串的長度，k 是不同字母的數量。
    • 統計頻率需要 O(n) 時間。
    • 將 k 個元素加入優先佇列需要 O(k log k) 時間。
    • 構建結果字串需要 O(n) 時間。
    • 總時間複雜度為 O(n + k log k + n)，由於 k 最多為 n，所以複雜度為 O(n log n)。
  • 空間複雜度：O(n)
    • 使用了 unordered_map 和 priority_queue，最壞情況下需要存儲 n 個元素。

方法二：桶排序（Bucket Sort）

  1. 統計字母頻率：使用 unordered_map 統計每個字母的出現次數。
  2. 建立桶：建立一個大小為 n + 1 的陣列 buckets，其中 buckets[i] 存放所有出現次數為 i 的字母。
  3. 構建結果字串：從高到低遍歷桶，將字母按照頻率添加到結果字串中。

詳細解釋

  • 統計字母頻率：
    • 同樣使用 unordered_map 來統計頻率。
  • 建立桶：
    • 創建一個大小為 n + 1 的陣列 buckets，索引對應頻率。
    • 對於每個字母，將其添加到對應頻率的桶中。
    • 由於一個字母最多出現 n 次，索引範圍為 1 到 n。
  • 構建結果字串：
    • 從高頻到低頻遍歷桶。
    • 如果桶不為空，將桶中的字母添加到結果字串中。

程式碼

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) 時間。
    • 將字母放入桶中需要 O(k) 時間，其中 k 是不同字母的數量，k <= n。
    • 構建結果字串需要 O(n) 時間。
    • 總時間複雜度為 O(n)。
  • 空間複雜度：O(n)
    • 使用了大小為 n + 1 的桶陣列，以及 unordered_map，總共需要 O(n) 空間。

Justin