排列給定數字以形成最大數| 系列 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** 編譯。如果發現任何不正確的地方，或者想分享有關上述主題的更多信息，請寫評論。