自定义排序构建最大数字：Java实现解析

本文探讨如何从给定的整数数组中构建出最大的数字。针对常见的数值排序和简单字典序排序的局限性，文章详细阐述了一种基于字符串拼接比较的自定义排序策略。通过比较任意两个数字拼接形成的两种字符串组合（AB与BA），我们能确定其在最终结果中的正确相对顺序，并提供完整的Java代码实现，帮助读者高效解决此类问题。

在编程挑战中，我们有时会遇到一个有趣的问题：给定一个整数数组，如何将这些整数拼接起来，以形成一个最大的数字。例如，对于输入数组 {10, 68, 75, 7, 21, 12}，期望的输出是 77568211210。这个问题看似简单，但其解决方案却需要巧妙的排序策略。

常见误区与挑战

初次尝试解决此问题时，开发者可能会自然地想到以下两种排序方法，但它们都无法得出正确结果：

1. 直接数值排序： 如果我们简单地将整数按照降序排列，然后拼接，例如 {75, 68, 21, 12, 10, 7} 拼接后得到 75682112107。这显然不是最大的数字，因为 7 应该放在 75 前面以形成 775，而非 757。

2. 简单字符串（字典序）排序： 将整数转换为字符串后，按照字典序进行降序排序。对于 {"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)。

这两种方法的问题在于，它们都未能考虑到数字在拼接后的全局影响。一个数字的“大小”不再是其本身的数值或字典序，而是它与其他数字拼接后所能贡献的最大值。

核心思想：自定义比较器

解决这个问题的关键在于定义一个特殊的比较规则，用于确定任意两个数字 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
    }
}

代码解析：

1. 转换为字符串： 首先，将整数数组中的所有数字转换为字符串。这是因为我们需要进行字符串拼接和字典序比较。
2. 自定义比较器：
   • 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 前面。
     • 如果相等，返回零。
   • 这种比较逻辑确保了具有更高“拼接优先级”的数字会排在前面。
3. 处理全零情况： 如果排序后的第一个字符串是 "0"，这意味着数组中所有数字都是零（例如 [0, 0, 0]）。在这种情况下，直接返回 "0" 即可，而不是 "000"。
4. 拼接结果： 最后，将排序好的字符串列表按顺序拼接起来，形成最终的最大数字字符串。

注意事项

• 数据类型转换： 必须将整数转换为字符串才能进行正确的拼接比较。
• 空数组/null 处理： 良好的实践是处理输入数组为空或 null 的情况，避免运行时错误。
• 全零数组： 考虑 [0, 0, 0] 这样的输入，期望输出是 0，而不是 000。代码中已包含此特殊处理。
• 效率： 这种方法的时间复杂度主要取决于排序算法。如果使用 Collections.sort（通常是 Timsort），其平均时间复杂度为 O(N log N)，其中 N 是数组中元素的数量。字符串拼接操作的复杂度与字符串长度相关，但对于一般整数，字符串长度不会过大。

总结

通过自定义比较器并利用字符串拼接比较的策略，我们能够有效地解决从整数数组构建最大数字的问题。这种方法巧妙地规避了简单数值排序和字典序排序的局限性，确保了在考虑数字组合时的全局最优解。理解这种比较逻辑是解决此类问题的关键，并且在多种编程语言中都可实现。