Programa en C++ para organizar números dados para formar el número más grande

Dada una serie de números, organícelos de manera que produzca el mayor valor. Por ejemplo, si los números dados son {54, 546, 548, 60}, el arreglo 6054854654 da el valor más grande. Y si los números dados son {1, 34, 3, 98, 9, 76, 45, 4}, entonces el arreglo 998764543431 da el mayor valor.

Una solución simple que nos viene a la mente es ordenar todos los números en orden descendente, pero simplemente ordenar no funciona. Por ejemplo, 548 es mayor que 60, pero en la salida 60 viene antes que 548. Como segundo ejemplo, 98 es mayor que 9, pero 9 viene antes que 98 en la salida.

Entonces, ¿cómo lo hacemos? La idea es utilizar cualquier algoritmo de clasificación basado en comparación . 
En el algoritmo de clasificación usado, en lugar de usar la comparación predeterminada, escriba una función de comparación myCompare() y utilícela para ordenar números. 

Dados dos números X e Y , ¿cómo debería myCompare() decidir qué número poner primero? Comparamos dos números XY (Y añadido al final de X) e YX (X añadido al final de Y). Si XY es más grande, entonces X debería aparecer antes que Y en la salida, de lo contrario, Y debería aparecer antes. Por ejemplo, sean X e Y 542 y 60. Para comparar X e Y, comparamos 54260 y 60542. Como 60542 es mayor que 54260, ponemos Y primero.

A continuación se muestra la implementación del enfoque anterior. 
Para mantener el código simple, los números se consideran strings, se usa el vector en lugar de una array normal. 

A continuación se muestra la implementación del enfoque anterior: 

// Given an array of numbers,
// program to arrange the numbers
// to form the largest number
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
using namespace std;
  
// A comparison function which 
// is used by sort() in
// printLargest()
int myCompare(string X, string Y)
{
    // first append Y at the end of X
    string XY = X.append(Y);
  
    // then append X at the end of Y
    string YX = Y.append(X);
  
    // Now see which of the two 
    // formed numbers is greater
    return XY.compare(YX) > 0 ? 1 : 0;
}
  
// The main function that prints 
// the arrangement with the
// largest value. The function 
// accepts a vector of strings
void printLargest(vector<string> arr)
{    
    // Sort the numbers using 
    // library sort function. The
    // function uses our comparison 
    // function myCompare() to
    // compare two strings. See
    // http://www.cplusplus.com/reference/
    // algorithm/sort/
    // for details
    sort(arr.begin(), arr.end(), myCompare);
  
    for (int i = 0; i < arr.size(); i++)
        cout << arr[i];
}
  
// Driver code
int main()
{
    vector<string> arr;
  
    // output should be 6054854654
    arr.push_back("54");
    arr.push_back("546");
    arr.push_back("548");
    arr.push_back("60");
    printLargest(arr);
  
    return 0;
}

Producción:

6054854654

Complejidad de tiempo:  O(nlogn), se considera que la clasificación tiene una complejidad de tiempo de ejecución de O(nlogn) y el ciclo for se ejecuta en tiempo O(n).
Espacio Auxiliar: O(1).

Consulte el artículo completo sobre Organizar números dados para formar el número más grande | ¡ Establezca 1 para más detalles!