算法题(如何排列给定数字以形成最大数(|S1))

本文概述

  • C ++
  • Java
  • Python3
  • C#
  • 的PHP
  • Python3
  • C ++
  • Java
  • Python3
  • C#
给定一个数字数组, 以产生最大值的方式排列它们。例如, 如果给定的数字为{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 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))】如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。

    推荐阅读