Sắp xếp các số đã cho để tạo thành số lớn nhất?

Ở đây chúng ta sẽ xem cách tạo ra số lớn nhất bằng cách sắp xếp lại các số đã cho. Giả sử có {45, 74, 23} được cho, chương trình sẽ tìm số lớn nhất, đó là 744523. Vì vậy mỗi chữ số sẽ không được sắp xếp. nhưng toàn bộ số sẽ được đặt để tạo thành số lớn nhất.

Để giải quyết vấn đề này, chúng tôi sẽ sử dụng sắp xếp chuỗi. Nhưng logic so sánh thì khác. Hàm so sánh sẽ nhận hai số a và b, sau đó ghép chúng lại để tạo thành ab và ba. Trong số đó cái nào lớn hơn, cái đó được xem xét.

Thuật toán

CompareStrings (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

Ví dụ

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

Đầu ra

744523