整数数组最大组合排序方法

本文详细探讨了如何从一个整数数组中构建出最大的组合数字。针对传统数值排序和简单字符串字典序排序的局限性，文章提出了一种基于字符串拼接比较的自定义排序算法。通过将数字转换为字符串并比较 `(a+b)` 与 `(b+a)` 的大小，我们能够确定最优的数字排列顺序，从而生成最终的最大组合数。文中提供了Java代码示例，并讨论了实现细节及注意事项。

理解“最大组合数”问题

“最大组合数”问题要求我们将一个给定的整数数组中的所有数字组合起来，形成一个最大的数字。例如，对于输入数组 {10, 68, 75, 7, 21, 12}，期望的输出是 77568211210。

初看之下，许多人可能会尝试直接对整数进行降序排序，或者将其转换为字符串后进行字典序降序排序。然而，这两种直观的方法都存在缺陷：

1. 直接数值降序排序： 如果我们直接对 {10, 68, 75, 7, 21, 12} 进行降序排序，得到 {75, 68, 21, 12, 10, 7}，组合起来是 75682112107。这显然不是最大的组合数，因为 7 放在 75 后面，会形成 757 而非 775。
2. 简单字符串字典序降序排序： 将数组元素转换为字符串后，如果直接进行字典序降序排序，例如 {"10", "68", "75", "7", "21", "12"}。
   • 比较 7 和 75：字典序上 75 大于 7。如果降序，75 会排在 7 前面。结果是 757...。但实际上 775... 更大，意味着 7 应该排在 75 前面。
   • 比较 1 和 10：字典序上 10 大于 1。如果降序，10 会排在 1 前面。结果是 101...。但实际上 110... 更大，意味着 1 应该排在 10 前面。

这些例子清楚地表明，我们需要一种特殊的比较逻辑来决定两个数字（作为字符串）在最终组合中的相对顺序。

核心算法：自定义比较器

解决“最大组合数”问题的关键在于设计一个自定义的比较器。对于任意两个数字 a 和 b（在转换为字符串后），我们不能简单地通过 a 或 b 的大小来判断它们的相对位置。正确的做法是，比较两种拼接方式的结果：ab（即 a 后面接 b）和 ba（即 b 后面接 a）。

比较规则： 如果字符串 ab 大于字符串 ba，那么 a 应该排在 b 的前面。 反之，如果 ba 大于 ab，那么 b 应该排在 a 的前面。

示例分析：

• 7 和 75：
  • ab = "7" + "75" = "775"
  • ba = "75" + "7" = "757"
  • 由于 "775" > "757"，所以 7 应该排在 75 的前面。
• 1 和 10：
  • ab = "1" + "10" = "110"
  • ba = "10" + "1" = "101"
  • 由于 "110" > "101"，所以 1 应该排在 10 的前面。

通过这种自定义的比较逻辑，我们可以确保在排序过程中，任何两个相邻数字的组合都能最大化局部值，进而推导出全局的最大组合数。

Java 实现示例

以下是使用Java语言实现这一逻辑的示例代码。我们将整数数组转换为字符串数组，然后使用 Arrays.sort() 方法结合自定义 Comparator 进行排序。

import java.util.Arrays;
import java.util.Comparator;

public class LargestNumberCombiner {

    /**
     * 从给定的整数数组中构建出最大的组合数字。
     *
     * @param nums 整数数组
     * @return 最大的组合数字字符串
     */
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return ""; // 处理空数组情况
        }

        // 1. 将整数转换为字符串数组
        String[] sNums = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            sNums[i] = String.valueOf(nums[i]);
        }

        // 2. 使用自定义比较器进行排序
        // 比较规则：对于任意两个字符串s1和s2，如果s1+s2 > s2+s1，则s1应该排在s2前面。
        // Arrays.sort默认是升序，所以如果s1+s2应该在s2+s1前面（即我们希望s1排在s2前面），
        // 那么比较器应该返回负数。
        // 等价于 (s2+s1).compareTo(s1+s2) 的结果，因为如果s2+s1更大，则返回正数，s2排在s1前面。
        // 我们希望s1+s2更大时，s1排在s2前面，所以返回 (s2+s1).compareTo(s1+s2)
        Arrays.sort(sNums, new Comparator() {
            @Override
            public int compare(String s1, String s2) {
                // 构建两种拼接方式的字符串
                String str1 = s1 + s2;
                String str2 = s2 + s1;
                // 使用字符串的compareTo方法进行字典序比较
                // 如果str2比str1大，返回正数，表示s2应该排在s1前面（降序逻辑）
                // 如果str1比str2大，返回负数，表示s1应该排在s2前面
                return str2.compareTo(str1);
            }
        });

        // 3. 处理全为0的特殊情况
        // 如果排序后的第一个数字是"0"，则表示所有数字都是0，结果应为"0"而不是"000..."
        if (sNums[0].equals("0")) {
            return "0";
        }

        // 4. 拼接排序后的字符串数组
        StringBuilder sb = new StringBuilder();
        for (String s : sNums) {
            sb.append(s);
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        LargestNumberCombiner combiner = new LargestNumberCombiner();

        int[] input1 = {10, 68, 75, 7, 21, 12};
        System.out.println("Input: " + Arrays.toString(input1) + ", Output: " + combiner.largestNumber(input1)); 
        // 期望输出: 77568211210

        int[] input2 = {3, 30, 34, 5, 9};
        System.out.println("Input: " + Arrays.toString(input2) + ", Output