将给定的数字排列成最大的数字|集1-yiteyi-C++库

给定一个数字数组，以产生最大值的方式排列它们。例如，如果给定的数字是{54，546，548，60}，则排列6054854654给出的值最大。如果给定的数字是{1,34,3,98,9,76,45,4}，那么排列998764543431给出的值最大。

null

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

A. 简单解决方案 我们想到的是按降序对所有数字进行排序，但简单地排序是行不通的。例如，548大于60，但在输出中，60在548之前。第二个例子是，98大于9，但在输出中9先于98。

那我们该怎么做呢？我们的想法是使用任何基于比较的排序算法。在使用的排序算法中，不要使用默认比较，而是编写一个比较函数 myCompare（） 并用它对数字进行排序。

给定两个数字十、和 Y 你应该怎么做 myCompare（） 决定先放哪个数字——我们比较两个数字XY（Y附加在X的末尾）和YX（X附加在Y的末尾）。如果 XY 越大，那么在输出中X应该在Y之前，否则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 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

                         # 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) & gt                       
                                                 int                                     (ab))                                     -                       
                                                 (                                     int                                     (ba) & lt                       
                                                 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) & lt                       
                                                 0                       
           
                                                 def                                     __gt__(                                     self                                     , other):                       
                                                 return                                     mycmp(                                     self                                     .obj, other.obj) & gt                       
                                                 0                       
           
                                                 def                                     __eq__(                                     self                                     , other):                       
                                                 return                                     mycmp(                                     self                                     .obj, other.obj)                                     =                                     =                                     0                       
           
                                                 def                                     __le__(                                     self                                     , other):                       
                                                 return                                     mycmp(                                     self                                     .obj, other.obj) & lt                       
                                                 =                                     0                       
           
                                                 def                                     __ge__(                                     self                                     , other):                       
                                                 return                                     mycmp(                                     self                                     .obj, other.obj) & gt                       
                                                 =                                     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 {                       
                                   
                                                 // 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>                       

输出

6054854654

时间复杂性： O（nlogn），分类被认为运行时间复杂度为O（nlogn），for循环在O（n）时间内运行。 辅助空间： O（1）。

另一种方法： （使用 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

时间复杂性： O（n！） 辅助空间： O（1）。

本文由 拉维·钱德拉·埃纳甘蒂 。如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请发表评论。

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章