สมมติว่าเรามีอาร์เรย์ของตัวเลข เราต้องหาจำนวนสูงสุดที่สามารถรับได้โดยใช้ตัวเลขทั้งหมดของอาร์เรย์ ดังนั้นหากอาร์เรย์เป็นแบบ [3, 3, 9, 6, 2, 5] จำนวนสูงสุดจะเป็น 965332
จากปัญหาจะเห็นว่าเราสามารถเรียงลำดับตัวเลขง่ายๆ แบบไม่เพิ่มขึ้นแล้วพิมพ์ออกมาได้ แต่เราสามารถแก้ปัญหานี้ได้โดยใช้วิธีที่มีประสิทธิภาพมากขึ้น เราสามารถสร้างอาร์เรย์ขนาด 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
