Giả sử chúng ta có một mảng các chữ số. Chúng ta phải tìm số lớn nhất có thể nhận được khi sử dụng tất cả các chữ số của mảng. Vì vậy, nếu mảng giống như [3, 3, 9, 6, 2, 5], thì số tối đa có thể là 965332.
Từ bài toán, chúng ta có thể dễ dàng sắp xếp các chữ số theo thứ tự không tăng dần, sau đó in ra. Nhưng chúng ta có thể giải quyết vấn đề này bằng cách hiệu quả hơn. Chúng ta có thể tạo một mảng có kích thước 10 để lưu trữ tần số của mỗi chữ số, sau đó in các số từ 9 đến 0 tương ứng.
Ví dụ
#include <iostream>
#include <string>
using namespace std;
int maxNumFromNum(int arr[], int n) {
int freq[10] = {0};
for (int i=0; i<n; i++)
freq[arr[i]]++;
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 digits[] = {3, 3, 9, 6, 2, 5};
int n = sizeof(digits)/sizeof(digits[0]);
cout << "Maximum number: " << maxNumFromNum(digits, n);
} Đầu ra
Maximum number: 965332