排列给定数字以形成最大数| 系列 1 · GeeksForGeeks 中文系列教程

# 排列给定数字以形成最大数| 系列 1 > 原文： [https://www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number/](https://www.geeksforgeeks.org/given-an-array-of-numbers-arrange-the-numbers-to-form-the-biggest-number/) 给定一个数字数组，以产生最大值的方式排列它们。例如，如果给定的数字为`{54, 546, 548, 60}`，则排列 6054854654 给出最大值。并且如果给定数字为`{1, 34, 3, 98, 9, 76, 45, 4}`，则排列 998764543431 给出最大值。我们想到的**简单解决方案**是对所有数字进行降序排序，但简单地排序是行不通的。例如，548 大于 60，但是输出 60 在 548 之前。第二个示例，98 大于 9，但是输出在 98 之前是 9。那么我们如何去做呢？这个想法是使用任何基于[比较的排序](https://www.geeksforgeeks.org/analysis-of-different-sorting-techniques/)算法。在使用的排序算法中，代替使用默认比较，编写比较函数`myCompare()`并使用它对数字进行排序。给定两个数字 **X** 和 **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++ ```cpp // Given an array of numbers, program to arrange the numbers to form the // largest number #include <iostream> #include <string> #include <vector> #include <algorithm> 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 ```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 ```py # 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# ```cs 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 <?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`](https://www.geeksforgeeks.org/itertools-combinations-module-python-print-possible-combinations/)）使用 Python 的内置库，可以使用`itertools`库执行此任务。 ``` # 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 ``` 本文由 **Ravi Chandra Enaganti** 编译。如果发现任何不正确的地方，或者想分享有关上述主题的更多信息，请写评论。