排列给定数字来生成最大数字 | 系列 1
给定一个数字数组，以产生最大值的方式排列它们。 例如，如果给定的数字为{54, 546, 548, 60}，则排列 6054854654 给出最大值。 并且如果给定数字为{1, 34, 3, 98, 9, 76, 45, 4}，则排列 998764543431 给出最大值。
我们想到的简单解决方案是对所有数字进行降序排序，但简单地排序是行不通的。 例如，548 大于 60，但是输出 60 在 548 之前。第二个示例，98 大于 9，但是输出在 98 之前是 9。
那么我们如何去做呢？ 这个想法是使用任何基于比较的排序算法。
在使用的排序算法中，代替使用默认比较，编写比较函数myCompare()并使用它对数字进行排序。
给定两个数字X和Y，myCompare()应该如何确定要放哪个数字–我们比较两个数字XY（Y附加在X的末尾）和YX（X附加在Y的末尾）。 如果XY较大，则在输出中X应该位于Y之前，否则Y应该位于X之前。 例如，令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 <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
// 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#
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 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
版权属于：月萌API www.moonapi.com，转载请注明出处
