本文概述
- C ++
- Java
- Python3
- C#
- 的PHP
- Python3
- C ++
- Java
- Python3
- C#
一种简单的解决方案我们想到的是按照降序对所有数字进行排序, 但是简单地排序是行不通的。例如, 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 Juneja
Python3
# 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 SaurabhTewary
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
{
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 gauravrajput1
Java
// 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 gauravrajput1
C#
// 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
【算法题(如何排列给定数字以形成最大数(|S1))】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。
推荐阅读
- 进程和线程之间有什么区别(详细讲解)
- 什么是JavaScript运算符以及如何使用它()
- 算法(如何排列给定数字以形成最大数(|S2))
- PHP如何使用Ds\Deque __construct()函数(用法实例)
- Python正则表达式(re.search() VS re.findall())
- 热点2.0(Hotspot 2.0)详细指南介绍
- BrowserStack面试体验|S6(校园内)
- Perl循环(foreach、foreach、while、do…while、until嵌套循环)
- 如何在Java 8中打印Stream的元素