本文探讨如何从给定的整数数组中构建出最大的数字。针对常见的数值排序和简单字典序排序的局限性，文章详细阐述了一种基于字符串拼接比较的自定义排序策略。通过比较任意两个数字拼接形成的两种字符串组合（ab与ba），我们能确定其在最终结果中的正确相对顺序，并提供完整的java代码实现，帮助读者高效解决此类问题。
在编程挑战中，我们有时会遇到一个有趣的问题：给定一个整数数组，如何将这些整数拼接起来，以形成一个最大的数字。例如，对于输入数组 {10, 68, 75, 7, 21, 12}，期望的输出是 77568211210。这个问题看似简单，但其解决方案却需要巧妙的排序策略。
常见误区与挑战
初次尝试解决此问题时，开发者可能会自然地想到以下两种排序方法，但它们都无法得出正确结果：
直接数值排序： 如果我们简单地将整数按照降序排列，然后拼接，例如 {75, 68, 21, 12, 10, 7} 拼接后得到 75682112107。这显然不是最大的数字，因为 7 应该放在 75 前面以形成 775，而非 757。
-
简单字符串（字典序）排序： 将整数转换为字符串后，按照字典序进行降序排序。对于 {"10", "68", "75", "7", "21", "12"}，字典序降序排列可能得到 {"75", "7", "68", "21", "12", "10"}。拼接后是 75768211210。这个结果仍然不正确，因为 77568211210 比 75768211210 更大。问题在于，当遇到像 7 和 75 这样的数字时，简单字典序无法正确判断它们的相对位置。单独看，75 大于 7；但放在一起，7 跟着 75 (775) 优于 75 跟着 7 (757)。
立即学习“Java免费学习笔记（深入）”；
这两种方法的问题在于，它们都未能考虑到数字在拼接后的全局影响。一个数字的“大小”不再是其本身的数值或字典序，而是它与其他数字拼接后所能贡献的最大值。
核心思想：自定义比较器
解决这个问题的关键在于定义一个特殊的比较规则，用于确定任意两个数字 a 和 b 在最终拼接结果中的相对顺序。这个规则基于以下洞察：
要判断 a 应该放在 b 的前面还是后面，我们应该比较两种拼接结果：
- 将 a 放在 b 前面形成的字符串 ab。
- 将 b 放在 a 前面形成的字符串 ba。
如果 ab 字符串在字典序上大于 ba 字符串，那么 a 就应该排在 b 的前面。反之，如果 ba 大于 ab，则 b 应该排在 a 的前面。
示例：
-
比较 7 和 75：
- ab = "7" + "75" = "775"
- ba = "75" + "7" = "757"
- 由于 "775" > "757"，所以 7 应该排在 75 的前面。
-
比较 10 和 68：
- ab = "10" + "68" = "1068"
- ba = "68" + "10" = "6810"
- 由于 "6810" > "1068"，所以 68 应该排在 10 的前面。
通过这种自定义的比较逻辑，我们可以确保每次比较都倾向于形成更大的拼接结果。
Java 实现
在 Java 中，我们可以利用 Collections.sort() 或 Arrays.sort() 方法，并传入一个自定义的 Comparator 来实现这种排序。
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;
import java.util.stream.Collectors;
public class LargestNumberCombiner {
/**
* 从给定的整数数组中构建最大的数字字符串。
*
* @param nums 整数数组
* @return 拼接后形成的最大数字字符串
*/
public static String findLargestCombination(int[] nums) {
if (nums == null || nums.length == 0) {
return "";
}
// 将整数转换为字符串数组，以便进行字符串拼接比较
List strNums = Arrays.stream(nums)
.mapToObj(String::valueOf)
.collect(Collectors.toList());
// 使用自定义比较器进行排序
// 比较器逻辑：对于任意两个字符串s1和s2，如果(s2+s1)大于(s1+s2)，
// 则s2应该排在s1前面，即s2“更大”。
// 这里使用s2+s1与s1+s2比较，是为了实现降序排列，
// 确保“更大”的组合排在前面。
strNums.sort(new Comparator() {
@Override
public int compare(String s1, String s2) {
String s1s2 = s1 + s2;
String s2s1 = s2 + s1;
// 降序排列，如果s2s1更大，则s2排在s1前面
return s2s1.compareTo(s1s2);
}
});
// 特殊情况：如果排序后第一个数字是'0'，说明所有数字都是0，
// 此时结果应为"0"而不是"000..."
if (strNums.get(0).equals("0")) {
return "0";
}
// 拼接所有排序后的字符串
StringBuilder result = new StringBuilder();
for (String s : strNums) {
result.append(s);
}
return result.toString();
}
public static void main(String[] args) {
int[] input1 = {10, 68, 75, 7, 21, 12};
System.out.println("Input: " + Arrays.toString(input1));
System.out.println("Output: " + findLargestCombination(input1)); // 期望: 77568211210
int[] input2 = {3, 30, 34, 5, 9};
System.out.println("Input: " + Arrays.toString(input2));
System.out.println("Output: " + findLargestCombination(input2)); // 期望: 9534330
int[] input3 = {0, 0, 0};
System.out.println("Input: " + Arrays.toString(input3));
System.out.println("Output: " + findLargestCombination(input3)); // 期望: 0
int[] input4 = {1};
System.out.println("Input: " + Arrays.toString(input4));
System.out.println("Output: " + findLargestCombination(input4)); // 期望: 1
}
} 代码解析：
- 转换为字符串： 首先，将整数数组中的所有数字转换为字符串。这是因为我们需要进行字符串拼接和字典序比较。
-
自定义比较器：
- strNums.sort(new Comparator
() {...}) 定义了一个匿名内部类作为比较器。 - 在 compare(String s1, String s2) 方法中，我们构建了两个临时字符串：s1s2 (s1 + s2) 和 s2s1 (s2 + s1)。
- s2s1.compareTo(s1s2)：这个方法返回一个整数，表示 s2s1 和 s1s2 在字典序上的关系。
- 如果 s2s1 大于 s1s2，返回正数，表示 s2 应该排在 s1 前面（降序）。
- 如果 s2s1 小于 s1s2，返回负数，表示 s1 应该排在 s2 前面。
- 如果相等，返回零。
- 这种比较逻辑确保了具有更高“拼接优先级”的数字会排在前面。
- strNums.sort(new Comparator
- 处理全零情况： 如果排序后的第一个字符串是 "0"，这意味着数组中所有数字都是零（例如 [0, 0, 0]）。在这种情况下，直接返回 "0" 即可，而不是 "000"。
- 拼接结果： 最后，将排序好的字符串列表按顺序拼接起来，形成最终的最大数字字符串。
注意事项
- 数据类型转换： 必须将整数转换为字符串才能进行正确的拼接比较。
- 空数组/null 处理： 良好的实践是处理输入数组为空或 null 的情况，避免运行时错误。
- 全零数组： 考虑 [0, 0, 0] 这样的输入，期望输出是 0，而不是 000。代码中已包含此特殊处理。
- 效率： 这种方法的时间复杂度主要取决于排序算法。如果使用 Collections.sort（通常是 Timsort），其平均时间复杂度为 O(N log N)，其中 N 是数组中元素的数量。字符串拼接操作的复杂度与字符串长度相关，但对于一般整数，字符串长度不会过大。
总结
通过自定义比较器并利用字符串拼接比较的策略，我们能够有效地解决从整数数组构建最大数字的问题。这种方法巧妙地规避了简单数值排序和字典序排序的局限性，确保了在考虑数字组合时的全局最优解。理解这种比较逻辑是解决此类问题的关键，并且在多种编程语言中都可实现。
