srcmini本文概述
给定一个数字数组, 以产生最大值的方式排列它们。例如, 如果给定的数字为{54, 546, 548, 60}, 则排列6054854654给出最大值。如果给定的数字为{1、34、3、98、9、76、45、4}, 则排列998764543431给出最大值。
一种简单的解决方案我们想到的是按照降序对所有数字进行排序, 但是简单地排序是行不通的。例如, 548大于60, 但是输出60在548之前。第二个示例, 98大于9, 但是9在输出98之前。
那我们该怎么做呢?其思想是使用任何基于比较的排序算法。
在已使用的排序算法中，不使用默认比较，而是编写一个比较函数myCompare()，并使用它对数字进行排序。
给定两个数字X和ÿ, 应该怎样myCompare()决定要放哪个数字–我们比较两个数字XY(在X末尾附加Y)和YX(在Y末尾附加X)。如果XY较大, 则在输出中X应该在Y之前, 否则Y应该在输出之前。例如, 让X和Y为542和60。要比较X和Y, 我们比较54260和60542。由于60542大于54260, 我们将Y放在第一位。
以下是上述方法的实现。
为了使代码简单, 将数字视为字符串, 使用向量代替常规数组。
下面是上述方法的实现：
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 program to test above functions
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 program
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 JunejaPython3
# Python3 Program to get the maximum
# possible integer from given array
# of integers...
# custom comparator to sort according
# to the ab, ba as mentioned in description
def comparator(a, b):
ab = str (a) + str (b)
ba = str (b) + str (a)
return (( int (ba) > int (ab)) -
( int (ba) < int (ab)))
def myCompare(mycmp):
# Convert a cmp= function into a key= function
class K( object ):
def __init__( self , obj, * args):
self .obj = obj
def __lt__( self , other):
return mycmp( self .obj, other.obj) < 0
def __gt__( self , other):
return mycmp( self .obj, other.obj) > 0
def __eq__( self , other):
return mycmp( self .obj, other.obj) = = 0
def __le__( self , other):
return mycmp( self .obj, other.obj) < = 0
def __ge__( self , other):
return mycmp( self .obj, other.obj) > = 0
def __ne__( self , other):
return mycmp( self .obj, other.obj) ! = 0
return K
# driver code
if __name__ = = "__main__" :
a = [ 54 , 546 , 548 , 60 , ]
sorted_array = sorted (a, key = myCompare(comparator))
number = "".join([ str (i) for i in sorted_array])
print (number)
# This code is Contributed by SaurabhTewaryC#
// 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
{
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
?>输出如下
6054854654另一种方法：(使用itertools)使用Python的内置库, itertools库可用于执行此任务。
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输出如下
6054854654另一种方法：使用内置排序方法, 下面是该方法的实现。
C ++
// C++ approach for the above approach
#include <bits/stdc++.h>
using namespace std;
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
void printLargest(vector<string> arr)
{
sort(arr.begin(), arr.end());
for ( int i = arr.size() - 1; i >= 0; 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);
}
// This code is contributed by gauravrajput1Java
// Java approach for the above approach
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, Collections.
reverseOrder());
Iterator it = arr.iterator();
while (it.hasNext())
System.out.print(it.next());
}
// Driver program
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);
}
}Python3
# Python3 approach for the
# above approach
# The main function that
# prints the arrangement
# with the largest value.
# The function accepts a
# vector of strings
def printLargest(arr):
arr.sort(reverse = True )
number = "".join([ str (i) for i in arr])
print (number)
# Driver code
if __name__ = = '__main__' :
arr = [ "54" , "546" , "548" , "60" ];
# Output should be 6054854654
printLargest(arr);
# This code is contributed by gauravrajput1C#
// C# approach for
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// The main function that prints the
// arrangement with the largest value.
// The function accepts a vector of strings
static void printLargest(List<String> arr)
{
arr.Sort();
arr.Reverse();
foreach (String str in arr)
Console.Write(str);
}
// Driver code
public static void Main(String[] args)
{
List<String> arr;
arr = new List<String>();
arr.Add( "54" );
arr.Add( "546" );
arr.Add( "548" );
arr.Add( "60" );
printLargest(arr);
}
}
// This code is contributed by Rajput-Ji输出如下
6054854654如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
评论前必须登录！
注册