สมมติว่ามีอาร์เรย์ของหลักเลข เราต้องหาตัวเลขสูงสุดที่สามารถได้จากการใช้หลักทั้งหมดของอาร์เรย์ ดังนั้นถ้าอาร์เรย์เป็น [3, 3, 9, 6, 2, 5] ตัวเลขสูงสุดคือ 965332
จากโจทย์ เราเห็นว่าเราสามารถเรียงหลักเลขในลำดับไม่เพิ่ม (Non-increasing) แล้วพิมพ์ได้ แต่เราสามารถแก้ได้ด้วยวิธีที่มีประสิทธิภาพมากขึ้น เราสามารถสร้างอาร์เรย์ขนาด 10 เพื่อเก็บความถี่ของแต่ละหลัก แล้วพิมพ์ตัวเลขจาก 9 ลงมา 0 ตามลำดับ
ตัวอย่าง
#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);
}
ผลลัพธ์
Maximum number: 965332
