หาตัวเลขสูงสุดที่สร้างจากหลักของตัวเลขที่กำหนดใน C++

โจทย์

ให้ตัวเลข N หลัก ต้องการจัดเรียงหลักตัวเลขใหม่ให้ได้ตัวเลขมากที่สุด

ตัวอย่าง: 339625 → 965332

วิธีแก้ปัญหา (Counting Sort - O(d))

แทนการเรียง (O(d log d)) ใช้อาร์เรย์นับความถี่ขนาด 10 (0-9):

1. นับความถี่แต่ละหลัก
2. พิมพ์จาก 9 ลงมา 0 ตามความถี่

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

#include <iostream>
#include <string>
using namespace std;

int maxNumFromNum(int num) {
    int freq[10] = {0};
    string str = to_string(num);
    for (int i = 0; i < str.length(); i++) freq[str[i] - '0']++;
    int res = 0, mul = 1;
    for (int i = 0; i <= 9; i++) {
        while (freq[i] > 0) {
            res = res + (i * mul);
            freq[i]--;
            mul = mul * 10;
        }
    }
    return res;
}

int main() {
    int num = 339625;
    cout << "Maximum number: " << maxNumFromNum(num);
}

ผลลัพธ์

Maximum number: 965332