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.
Para Python, el procedimiento se explica en la función número más grande() .
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:
C++
// 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;
}
Java
// Given an array of numbers, program to
// arrange the numbers to form the
// largest number
import java.util.*;
class GFG {
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
static void printLargest(Vector<String> arr)
{
Collections.sort(arr, new Comparator<String>()
{
// A comparison function which is used by
// sort() in printLargest()
@Override public int compare(String X, String Y)
{
// first append Y at the end of X
String XY = X + Y;
// then append X at the end of Y
String YX = Y + X;
// Now see which of the two
// formed numbers
// is greater
return XY.compareTo(YX) > 0 ? -1 : 1;
}
});
Iterator it = arr.iterator();
while (it.hasNext())
System.out.print(it.next());
}
// Driver code
public static void main(String[] args)
{
Vector<String> arr;
arr = new Vector<>();
// output should be 6054854654
arr.add("54");
arr.add("546");
arr.add("548");
arr.add("60");
printLargest(arr);
}
}
// This code is contributed by Shubham Juneja
Python3
def largestNumber(array): #If there is only one element in the list, the element itself is the largest element. #Below if condition checks the same. if len(array)==1: return str(array[0]) #Below lines are code are used to find the largest element possible. #First, we convert a list into a string array that is suitable for concatenation for i in range(len(array)): array[i]=str(array[i]) # [54,546,548,60]=>['54','546','548','60'] #Second, we find the largest element by swapping technique. for i in range(len(array)): for j in range(1+i,len(array)): if array[j]+array[i]>array[i]+array[j]: array[i],array[j]=array[j],array[i] #['60', '548', '546', '54'] #Refer JOIN function in Python result=''.join(array) #Edge Case: If all elements are 0, answer must be 0 if(result=='0'*len(result)): return '0' else: return result if __name__ == "__main__": a = [54, 546, 548, 60] print(largestNumber(a))
C#
// C# program for above approach
using System.Collections.Generic;
using System;
namespace LargestNumberClass {
class LargestNumberClass {
// Given a list of non-negative
// integers,
// arrange them such that they
// form the largest number.
// Note: The result may be very
// large, so you need to
// return a string instead
// of an integer.
public static void
LargestNumberMethod(List<int> inputList)
{
string output = string.Empty;
List<string> newList = inputList.ConvertAll<string>(
delegate(int i) { return i.ToString(); });
newList.Sort(MyCompare);
for (int i = 0; i < inputList.Count; i++)
{
output = output + newList[i];
}
if (output[0] == '0' && output.Length > 1)
{
Console.Write("0");
}
Console.Write(output);
}
internal static int MyCompare(string X, string Y)
{
// first append Y at the end of X
string XY = X + Y;
// then append X at the end of Y
string YX = Y + X;
// Now see which of the two
// formed numbers is greater
return XY.CompareTo(YX) > 0 ? -1 : 1;
}
}
class Program {
// Driver code
static void Main(string[] args)
{
List<int> inputList
= new List<int>() { 54, 546, 548, 60 };
LargestNumberClass.LargestNumberMethod(inputList);
}
}
// This code is contributed by Deepak Kumar Singh
}
PHP
<?php
// Given an array of numbers, program
// to arrange the numbers to form the
// largest number
// A comparison function which is used
// by sort() in printLargest()
function myCompare($X, $Y)
{
// first append Y at the end of X
$XY = $Y.$X;
// then append X at the end of Y
$YX = $X.$Y;
// Now see which of the two formed
// numbers is greater
return strcmp($XY, $YX) > 0 ? 1: 0;
}
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
function printLargest($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
usort($arr, "myCompare");
for ($i = 0; $i < count($arr) ; $i++ )
echo $arr[$i];
}
// Driver Code
$arr = array("54", "546", "548", "60");
printLargest($arr);
// This code is contributed by
// rathbhupendra
?>
Javascript
<script>
// Given an array of numbers,
// program to arrange the numbers
// to form the largest number
// A comparison function which
// is used by sort() function in
// printLargest()
function myCompare(X, Y)
{
// // first append Y at the end of X
let XY = X + Y;
// // then append X at the end of Y
let YX = Y + X;
// // Now see which of the two
// // formed numbers is greater
return (YX - XY)
}
// The main function that prints
// the arrangement with the
// largest value. The function
// accepts a vector of strings
function printLargest(arr)
{
// Sort the numbers using
// inbuilt sort function. The
// function uses our comparison
// function myCompare() to
// compare two strings.
arr.sort(myCompare);
for(let i = 0; i < arr.length; i++)
document.write(arr[i])
// join method creates a string out of the array elements.
document.write(arr.join(""))
}
// Driver code
let arr = [];
// output should be 6054854654
arr.push("54");
arr.push("546");
arr.push("548");
arr.push("60");
printLargest(arr);
// This code is contributed by shinjanpatra
</script>
Producción
6054854654
En la solución anterior, se nos permiten entradas de strings, pero en caso de que las strings estén restringidas, también podemos resolver el problema anterior usando long long int para encontrar el arreglo más grande. La única limitación es que no podemos almacenar números mayores de 10^18 . En caso de que exceda eso, la solución anterior será la única opción.
C++14
// 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;
typedef long long ll;
// A comparison function which
// is used by sort() in
// printLargest()
bool myCompare(int x, int y)
{
int xy = x, yx = y;
// Count length of x and y
int countx = 0, county = 0;
// Count length of X
while (x > 0) {
countx++;
x /= 10;
}
// Count length of Y
while (y > 0) {
county++;
y /= 10;
}
x = xy;
y = yx;
while (countx--)
yx *= 10;
while (county--)
xy *= 10;
// Append x to y
yx += x;
// Append y to x
xy += y;
return xy > yx;
}
// The main function that prints
// the arrangement with the
// largest value. The function
// accepts a vector of strings
void printLargest(vector<ll> 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<ll> 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;
}
// this code is contributed by prophet1999
Java
// Given an array of numbers,
// program to arrange the numbers
// to form the largest number
import java.util.*;
public class GFG
{
// The main function that prints
// the arrangement with the
// largest value. The function
// accepts a vector of strings
static void printLargest(ArrayList<Integer> arr)
{
// Sort the numbers using
// library sort function. The
// function uses our comparison
// function myCompare() to
// compare two strings.
Collections.sort(arr, new Comparator<Integer>(){
// A comparison function which
// is used by sort() in
// printLargest()
@Override
public int compare(Integer x, Integer y)
{
int xy = x;
int yx = y;
// Count length of x and y
int countx = 0;
int county = 0;
// Count length of X
while (x > 0) {
countx++;
x /= 10;
}
// Count length of Y
while (y > 0) {
county++;
y /= 10;
}
x = xy;
y = yx;
while (countx > 0)
{
countx--;
yx *= 10;
}
while (county > 0)
{
county--;
xy *= 10;
}
// Append x to y
yx += x;
// Append y to x
xy += y;
return -xy + yx;
}
});
for (int i = 0; i < arr.size(); i++)
System.out.print(arr.get(i));
}
// Driver code
public static void main(String[] args)
{
// Output should be 6054854654
ArrayList<Integer> arr = new ArrayList<>();
arr.add(54);
arr.add(546);
arr.add(548);
arr.add(60);
printLargest(arr);
}
}
// this code is contributed by phasing17
Python3
# Python3 program to arrange the
# given array of numbers
# to form the largest number
import functools
# A comparison function which
# is used by sort() in
# printLargest()
def myCompare(x, y):
xy = x
yx = y
# Count length of x and y
countx = 0
county = 0
# Count length of X
while (x > 0):
countx += 1
x //= 10
# Count length of Y
while (y > 0):
county += 1
y //= 10
x = xy
y = yx
while (countx):
countx -= 1
yx *= 10
while (county):
county -= 1
xy *= 10
# Append x to y
yx += x
# Append y to x
xy += y
return 1 if xy > yx else -1
# The main function that prints
# the arrangement with the
# largest value. The function
# accepts a vector of strings
def printLargest(arr):
# Sort the numbers using
# library sort function. The
# function uses our comparison
# function myCompare() to
# compare two strings. See
arr.sort(key=functools.cmp_to_key(myCompare))
arr.reverse()
print("".join(map(str, arr)))
# Driver code
arr = [54, 546, 548, 60]
# Function Hall
printLargest(arr)
# This code is contributed by phasing17
C#
// Given an array of numbers,
// program to arrange the numbers
// to form the largest number
using System;
using System.Collections.Generic;
class myCompare : Comparer<int>
{
// A comparison function which
// is used by sort() in
// printLargest()
public override int Compare(int x, int y)
{
int xy = x;
int yx = y;
// Count length of x and y
int countx = 0;
int county = 0;
// Count length of X
while (x > 0) {
countx++;
x /= 10;
}
// Count length of Y
while (y > 0) {
county++;
y /= 10;
}
x = xy;
y = yx;
while (countx > 0) {
countx--;
yx *= 10;
}
while (county > 0) {
county--;
xy *= 10;
}
// Append x to y
yx += x;
// Append y to x
xy += y;
return -xy + yx;
}
};
public class GFG {
// The main function that prints
// the arrangement with the
// largest value. The function
// accepts a vector of strings
static void printLargest(List<int> arr)
{
// Sort the numbers using
// library sort function. The
// function uses our comparison
// function myCompare() to
// compare two strings.
arr.Sort(new myCompare());
for (int i = 0; i < arr.Count; i++)
Console.Write(arr[i]);
}
// Driver code
public static void Main(string[] args)
{
// Output should be 6054854654
List<int> arr = new List<int>();
arr.Add(54);
arr.Add(546);
arr.Add(548);
arr.Add(60);
printLargest(arr);
}
}
// This code is contributed by phasing17
Javascript
// Given an array of numbers,
// JavaScript program to arrange the numbers
// to form the largest number
// A comparison function which
// is used by sort() in
// printLargest()
function myCompare(x, y)
{
let xy = x;
let yx = y;
// Count length of x and y
let countx = 0;
let county = 0;
// Count length of X
while (x > 0) {
countx++;
x = Math.floor(x / 10);
}
// Count length of Y
while (y > 0) {
county++;
y = Math.floor(y / 10);
}
x = xy;
y = yx;
while (countx--)
yx *= 10;
while (county--)
xy *= 10;
// Append x to y
yx += x;
// Append y to x
xy += y;
return xy < yx;
}
// The main function that prints
// the arrangement with the
// largest value. The function
// accepts a vector of strings
function printLargest(arr)
{
// Sort the numbers using
// library sort function. The
// function uses our comparison
// function myCompare() to
// compare two strings
arr.sort(myCompare);
for (var i = 0; i < arr.length; i++)
process.stdout.write(arr[i].toString());
}
// Driver code
let arr = [];
// Output should be 6054854654
arr.push(54);
arr.push(546);
arr.push(548);
arr.push(60);
printLargest(arr);
// this code is contributed by phasing17
Producción
6054854654
Complejidad de tiempo: O(n logn), se considera que la clasificación tiene una complejidad de tiempo de ejecución de O(n logn), y el bucle for se ejecuta en el tiempo O(n).
Espacio Auxiliar: O(1)
Otro enfoque: (usando itertools )
Usando la biblioteca incorporada de Python, la biblioteca itertools se puede usar para realizar esta tarea.
Python3
# Python3 implementation this is to use itertools.
# permutations as coded below:
from itertools import permutations
def largest(l):
lst = []
for i in permutations(l, len(l)):
# provides all permutations of the list values,
# store them in list to find max
lst.append("".join(map(str,i)))
return max(lst)
print(largest([54, 546, 548, 60])) #Output 6054854654
# This code is contributed by Raman Monga
Producción
6054854654
Complejidad Temporal: O(n!)
Espacio Auxiliar: O(1).
Este artículo fue compilado por Ravi Chandra Enaganti y mejorado por Prophet1999 . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA