จัดเรียงตัวเลขที่กำหนดเพื่อสร้างจำนวนที่มากที่สุด?

ที่นี่เราจะมาดูวิธีการสร้างจำนวนที่มากที่สุดโดยการจัดเรียงตัวเลขที่กำหนดใหม่ สมมติว่ามี {45, 74, 23} โปรแกรมจะค้นหาจำนวนที่มากที่สุด นั่นคือ 744523 ดังนั้นแต่ละหลักจะไม่ถูกจัดเรียง แต่จะใส่จำนวนเต็มให้เป็นจำนวนที่มากที่สุด

เพื่อแก้ปัญหานี้ เราจะใช้การเรียงลำดับสตริง แต่ตรรกะการเปรียบเทียบนั้นแตกต่างกัน ฟังก์ชันเปรียบเทียบจะใช้ตัวเลขสองตัว a และ b จากนั้นนำมาเชื่อมกันเพื่อสร้าง ab และ ba ในบรรดาพวกเขาที่หนึ่งที่ใหญ่กว่าที่ถือว่าเป็น.

อัลกอริทึม

เปรียบเทียบสตริง (a, b)

begin
   ab := concatenate b with a
   ba := concatenate a with b
   compare ba with ab, then return 1 if ba is bigger, otherwise return 0
end
getLargest(arr):
begin
   sort the arr with the comparison logic using compareString()
   for each string s in arr, do
      print s
   done
end

ตัวอย่าง

#include<iostream>
#include <string>
#include &t;vector>
#include <algorithm>
using namespace std;
int stringCompare(string a, string b) {
   string ab = a.append(b);
   string ba = b.append(a);
   return ab.compare(ba) > 0 ? 1: 0;
}
void getLargest(vector<string> arr) {
   sort(arr.begin(), arr.end(), stringCompare); //sort the array
   for (int i =0; i < arr.size() ; i++ )
      cout << arr[i];
}
int main() {
   vector<string> arr;
   arr.push_back("45");
   arr.push_back("74");
   arr.push_back("23");
   getLargest(arr);
}

ผลลัพธ์

744523