Java 中从给定数组构建最大数字

这个问题是顶尖 IT 公司（如 Google、Facebook、Amazon 和 Microsoft）在编码阶段面试中最常问到的著名问题。在本节中，我们将创建 Java 程序（使用不同的逻辑）来从给定数组中构造最大数。

示例

输入 {10, 68, 75, 7, 21, 12}

输出 77568211210

从上面给出的数组，我们可以构造出可能的最大数 77568211210。请注意，数字的附加顺序无关紧要。

注意：数组中不应包含负数。

问题的解决方案

简单地将数组按降序排序，然后将该排序顺序视为所需结果是不可行的，因为这可能不是最大的数字。

首先，我们将为排序例程创建一个自定义比较器函数，该函数将比较两种配对比较（即 XY 和 YX），并且较大的数字将首先出现在排序顺序中。请注意，这里我们不需要单独比较 X 和 Y。

Java 程序：从给定数组构造最大数

LargestNumber.java

输出

 The largest number is: 908775854342160

上述程序的复杂度为O(nlogn)。其中 n 是输入大小。

让我们看看相同的另一个逻辑。

在下面的 Java 程序中，我们将每个数组元素转换为字符串。因为在将每个数字附加在一起后，我们会得到一个很大的数字，所以如果数组包含更多数字，最好将数字转换为字符串。之后，我们对数组进行了排序（降序）。将数组按降序排序可能会导致问题，即一组具有相同前导数字的数字。

例如，考虑一个数组{3, 30, 34, 5, 9}。

当我们将上述数组按降序排序时，它构造出的最大数为 9534303。但这并不是正确的答案。通过转置 33 和 3030 可以获得正确的答案。

因此，在执行排序时，请比较（对于每个配对比较）将该对按两种顺序连接而成的数字。数组排序后，我们将得到所需的最大数字。

可能存在数组包含零的情况。在这种情况下，如果最高有效数字是 00，则返回 00。否则，返回排序后的数组作为最大数字。

让我们在 Java 程序中实现上述逻辑。

LargestNumber.java

输出

The constructed largest number is:908775854342160

对于上述解决方案，时间复杂度为O(nlogn)，空间复杂度为O(n)，因为我们使用了额外的空间来存储数字。