排列给定数字形成最大数字的 Java 程序
给定一组数字，以产生最大值的方式排列它们。例如，如果给定的数字是{54，546，548，60}，则排列 6054854654 给出最大值。如果给定的数字是{1，34，3，98，9，76，45，4}，那么排列 998764543431 给出最大值。
我们想到的一个简单的解决方法就是把所有的数字按照降序排序，但是单纯的排序是行不通的。例如，548 大于 60，但在输出中 60 在 548 之前。作为第二个例子，98 大于 9，但是在输出中 9 在 98 之前。
那我们该怎么做呢？想法是使用任何基于比较的排序算法。 在使用的排序算法中，不使用默认的比较，而是编写一个比较函数 myCompare() 并用它来排序数字。
给定两个数字 X 和 Y ，那么 myCompare() 应该如何决定先放哪个数字——我们比较两个数字 XY (Y 附加在 X 的末尾)和 YX (X 附加在 Y 的末尾)。如果 XY 比较大，那么输出中 X 应该在 Y 之前，否则 Y 应该在之前。例如，让 X 和 Y 分别为 542 和 60。为了比较 X 和 Y，我们比较了 54260 和 60542。因为 60542 大于 54260，所以我们把 Y 放在第一位。
下面是上述方法的实现。 为了保持代码简单，数字被视为字符串，使用向量代替普通数组。
下面是上述方法的实现:
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
输出:
6054854654
时间复杂度:O(nlogn)排序被认为运行时间复杂度为 O(nlogn)，for 循环在 O(n)时间内运行。 辅助空间: O(1)。
更多详情请参考整篇文章排列给定数字形成最大数字|集合 1 ！
版权属于：月萌API www.moonapi.com，转载请注明出处
