Tìm số lớn nhất tạo được từ các chữ số của một số cho trước trong C++

Cho một số có n chữ số. Cần tìm số lớn nhất có thể tạo được bằng cách sử dụng tất cả các chữ số của số đó. Ví dụ: số 339625, số lớn nhất là 965332.

Cách đơn giản: sắp xếp các chữ số theo thứ tự không tăng dần. Cách hiệu quả hơn: tạo mảng tần suất kích thước 10 để đếm số lần xuất hiện của mỗi chữ số, sau đó in từ 9 xuống 0 theo tần suất.

Ví dụ

#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);
}

Kết quả

Maximum number: 965332