Sort Characters By Frequency ใน C++

ตัวอย่าง: s = "abbbacbcc"

ความถี่: b:4, c:3, a:2

ผลลัพธ์: "bbbbcccaa"

อัลกอริทึม: Counting + Sorting

1. นับความถี่แต่ละตัวอักษรด้วย unordered_map<char, int> หรือ array[256]
2. เก็บคู่ (frequency, character) ลงใน vector
3. เรียง vector ตาม frequency มากไปน้อย (descending)
4. สร้างสตริงผลลัพธ์โดยทำซ้ำตัวอักษรตามความถี่

ตัวอย่างโค้ด C++

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    static bool cmp(const pair<int, char>& a, const pair<int, char>& b) {
        return a.first > b.first; // เรียง frequency มากไปน้อย
    }
    
    string frequencySort(string s) {
        unordered_map<char, int> freq;
        for (char c : s) freq[c]++;
        
        vector<pair<int, char>> v;
        for (auto& p : freq) {
            v.push_back({p.second, p.first});
        }
        
        sort(v.begin(), v.end(), cmp);
        
        string ans;
        for (auto& p : v) {
            ans.append(p.first, p.second); // append(char, count)
        }
        return ans;
    }
};

int main() {
    Solution ob;
    cout << ob.frequencySort("abbbacbcc") << endl;
    return 0;
}

Input

"abbbacbcc"

Output

bbbbcccaa

ความซับซ้อน (Complexity)

• เวลา: O(n + k log k) โดย n = ความยาวสตริง, k = จำนวนตัวอักษรที่แตกต่างกัน (≤ 256)
• พื้นที่: O(k)

วิธีอื่น (Bucket Sort) O(n): เนื่องจาก frequency สูงสุด = n สร้าง bucket[ n+1 ] เก็บตัวอักษรที่มีความถี่เท่ากัน แล้ววนจาก n ลง 0

// Bucket Sort version O(n)
string frequencySort(string s) {
    vector<int> freq(256, 0);
    for (char c : s) freq[c]++;
    
    vector<vector<char>> bucket(s.size() + 1);
    for (int i = 0; i < 256; i++) {
        if (freq[i] > 0) bucket[freq[i]].push_back(char(i));
    }
    
    string ans;
    for (int f = s.size(); f >= 1; f--) {
        for (char c : bucket[f]) {
            ans.append(f, c);
        }
    }
    return ans;
}

แก้ไขจากโค้ดต้นฉบับ: โค้ดต้นฉบับใช้ map (ซึ่งเรียงตาม key อัตโนมัติ) และ sort(v.rbegin(), v.rend(), cmp) ซึ่งซับซ้อนเกินไป ได้ลดรูปให้ชัดเจนกว่า