Sắp xếp các số cho trước để 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 trước. Giả sử có {45, 74, 23}, 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 riêng lẻ mà toàn bộ số sẽ được đặt để tạo thành số lớn nhất.

Để giải quyết bài toán này, chúng ta sẽ dùng sắp xếp chuỗi. Nhưng logic so sánh khác. Hàm so sánh sẽ lấy hai số a và b, sau đó nối chúng thành ab và ba. Trong số đó cái nào lớn hơn sẽ được ưu tiên.

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

Kết quả

744523