排序算法之：自定义排序规则——“将数组排成最大的数”
字数 2418 2025-12-21 09:20:57

好的，我注意到任务调度器相关的算法你已经学习过。今天我们来讲解一个与特定排序条件相关的有趣问题。

排序算法之：自定义排序规则——“将数组排成最大的数”

题目描述

给你一个非负整数数组 nums。你的任务是重新排列这些数的顺序（每个数不可拆分），使得它们连接起来形成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10, 2]
输出："210"
解释：210 是由 "2" + "10" 拼接而成，它比 "102"（"10" + "2"）大。

示例 2：

输入：nums = [3, 30, 34, 5, 9]
输出："9534330"
解释：注意，输出 "9534330" 是由数字 "9"、"5"、"34"、"3"、"30" 按顺序拼接而成。

示例 3：

输入：nums = [0, 0]
输出："0"
解释：如果结果只是多个 "0"，那么最终结果应该返回单个 "0"。

这个问题的核心挑战在于，我们不能简单地按数字的数值大小排序，而是需要定义一种新的、基于字符串拼接结果的“大小”关系。

解题过程

第一步：理解问题的核心——定义新的比较规则

我们先思考一个简单例子：nums = [a, b]。我们希望比较 ab 和 ba 哪个更大。

  • 如果 ab > ba，那么 a 应该排在 b 前面。
  • 如果 ab < ba，那么 b 应该排在 a 前面。
  • 如果 ab == ba，那么 a 和 b 谁前谁后都一样。

例如：a=3, b=30。

  • ab = "330"
  • ba = "303"
  • 因为 330 > 303，所以 3 应该排在 30 前面。这和我们直觉上认为 30 > 3 是不同的！

因此，我们排序的依据不再是数字本身的数值大小，而是对于任意两个数 x 和 y，比较 x + y 和 y + x 的字典序（或数值大小）。

第二步：将思路转化为算法步骤

  1. 转换：将所有整数转换为字符串（方便进行拼接比较）。
  2. 排序：使用自定义的比较器（Comparator）对字符串数组进行排序。比较规则是：对于字符串 s1 和 s2，如果 s1 + s2 > s2 + s1，则 s1 应该排在 s2 前面（在大多数排序库中，这意味着返回一个负值或 true 表示 s1 在 s2 之前）。
  3. 拼接：将排序后的字符串数组按顺序拼接成一个大的字符串。
  4. 处理前导零：由于数组可能包含多个 0，排序后最大的“数”可能是 "000..."。根据题目要求，我们需要将这种情况转换为 "0"。

第三步：深入剖析排序规则的正确性

为什么这种自定义的排序规则能保证最终得到最大的拼接数？

传递性：一个好的排序规则需要满足传递性（Transitivity），即如果 A 应排在 B 前 (AB > BA)，且 B 应排在 C 前 (BC > CB)，那么 A 应排在 C 前 (AC > CA)。幸运的是，我们定义的字符串拼接比较是满足传递性的（基于字符串字典序比较或数值比较），这保证了排序结果是唯一确定的。

贪心思想：我们可以将最终的最大拼接数看作是由一个个“局部最优”的相邻对构成的。如果存在相邻的一对数 X 和 Y，使得 XY < YX，那么我们交换它们的位置（变成 Y 和 X）就能得到一个更大的整体数字。我们的排序规则恰好保证了任意相邻的数 X 和 Y 都满足 XY >= YX（当数组降序排序时），即达到了局部最优，从而整体也是最优的。

第四步：算法实现与细节

让我们以示例 nums = [3, 30, 34, 5, 9] 来逐步推演：

  1. 转为字符串数组：["3", "30", "34", "5", "9"]。
  2. 应用自定义比较器排序（假设按降序排列，即大的在前）：
    • 比较 "3" 和 "30"："330" > "303"，所以 "3" 在 "30" 前面。
    • 比较 "30" 和 "34"："3034" < "3430"，所以 "34" 在 "30" 前面。
    • 比较 "34" 和 "5"："345" < "534"，所以 "5" 在 "34" 前面。
    • 比较 "5" 和 "9"："59" < "95"，所以 "9" 在 "5" 前面。
    • 排序过程中，排序算法（如快速排序）会递归地进行这些比较，最终确定顺序。
  3. 排序后的字符串数组为：["9", "5", "34", "3", "30"]。
  4. 将它们拼接："9" + "5" + "34" + "3" + "30" = "9534330"。
  5. 检查前导零："9534330" 第一位不是 '0'，所以直接返回。

边界情况处理：

  • 全零数组：nums = [0, 0, 0]。排序后得到 ["0", "0", "0"]，拼接为 "000"。根据规则，我们需要返回 "0"。一个简单的处理方法是：在最终拼接结果后，检查第一个字符是否为 '0'。如果是，说明整个字符串都是 '0'，直接返回 "0"。

第五步：复杂度分析

  • 时间复杂度：O(n log n * k)。其中 n 是数组长度，k 是数组中数字转换为字符串后的最大长度。排序需要进行 O(n log n) 次比较，每次比较（字符串拼接）的时间复杂度是 O(k)。
  • 空间复杂度：O(n)。主要用于存储字符串数组。

总结

这个题目巧妙地避开了传统的数值排序，要求我们根据拼接结果来定义新的序关系。解题的关键步骤是：

  1. 洞察核心：发现决定顺序的是 xy 和 yx 的比较结果。
  2. 定义规则：将数字转为字符串，并基于 s1+s2 与 s2+s1 的比较结果定义排序规则。
  3. 实施排序：使用任何基于比较的排序算法（如快速排序、归并排序），并传入自定义比较器。
  4. 处理细节：注意全零数组的特殊情况，返回 "0"。

它本质上是一种基于自定义比较规则的排序，是排序算法思想的一个非常灵活和实用的应用场景。

好的，我注意到任务调度器相关的算法你已经学习过。今天我们来讲解一个与特定排序条件相关的有趣问题。 排序算法之：自定义排序规则——“将数组排成最大的数” 题目描述 给你一个非负整数数组 nums 。你的任务是重新排列这些数的顺序（每个数不可拆分），使得它们连接起来形成一个最大的整数。 注意 ：输出结果可能非常大，所以你需要返回一个字符串而不是整数。 示例 1： 示例 2： 示例 3： 这个问题的核心挑战在于，我们不能简单地按数字的数值大小排序，而是需要定义一种新的、基于字符串拼接结果的“大小”关系。 解题过程 第一步：理解问题的核心——定义新的比较规则 我们先思考一个简单例子： nums = [a, b] 。我们希望比较 ab 和 ba 哪个更大。 如果 ab > ba ，那么 a 应该排在 b 前面。 如果 ab < ba ，那么 b 应该排在 a 前面。 如果 ab == ba ，那么 a 和 b 谁前谁后都一样。 例如： a=3 , b=30 。 ab = "330" ba = "303" 因为 330 > 303 ，所以 3 应该排在 30 前面。这和我们直觉上认为 30 > 3 是不同的！ 因此， 我们排序的依据不再是数字本身的数值大小，而是对于任意两个数 x 和 y ，比较 x + y 和 y + x 的字典序（或数值大小） 。 第二步：将思路转化为算法步骤 转换 ：将所有整数转换为字符串（方便进行拼接比较）。 排序 ：使用自定义的比较器（Comparator）对字符串数组进行排序。比较规则是：对于字符串 s1 和 s2 ，如果 s1 + s2 > s2 + s1 ，则 s1 应该排在 s2 前面（在大多数排序库中，这意味着返回一个负值或 true 表示 s1 在 s2 之前）。 拼接 ：将排序后的字符串数组按顺序拼接成一个大的字符串。 处理前导零 ：由于数组可能包含多个 0 ，排序后最大的“数”可能是 "000..." 。根据题目要求，我们需要将这种情况转换为 "0" 。 第三步：深入剖析排序规则的正确性 为什么这种自定义的排序规则能保证最终得到最大的拼接数？ 传递性 ：一个好的排序规则需要满足传递性（Transitivity），即如果 A 应排在 B 前 ( AB > BA )，且 B 应排在 C 前 ( BC > CB )，那么 A 应排在 C 前 ( AC > CA )。幸运的是，我们定义的字符串拼接比较是满足传递性的（基于字符串字典序比较或数值比较），这保证了排序结果是唯一确定的。 贪心思想 ：我们可以将最终的最大拼接数看作是由一个个“局部最优”的相邻对构成的。如果存在相邻的一对数 X 和 Y ，使得 XY < YX ，那么我们交换它们的位置（变成 Y 和 X ）就能得到一个更大的整体数字。我们的排序规则恰好保证了任意相邻的数 X 和 Y 都满足 XY >= YX （当数组降序排序时），即达到了局部最优，从而整体也是最优的。 第四步：算法实现与细节 让我们以示例 nums = [3, 30, 34, 5, 9] 来逐步推演： 转为字符串数组： ["3", "30", "34", "5", "9"] 。 应用自定义比较器排序（假设按降序排列，即大的在前）： 比较 "3" 和 "30" ： "330" > "303" ，所以 "3" 在 "30" 前面。 比较 "30" 和 "34" ： "3034" < "3430" ，所以 "34" 在 "30" 前面。 比较 "34" 和 "5" ： "345" < "534" ，所以 "5" 在 "34" 前面。 比较 "5" 和 "9" ： "59" < "95" ，所以 "9" 在 "5" 前面。 排序过程中，排序算法（如快速排序）会递归地进行这些比较，最终确定顺序。 排序后的字符串数组为： ["9", "5", "34", "3", "30"] 。 将它们拼接： "9" + "5" + "34" + "3" + "30" = "9534330" 。 检查前导零： "9534330" 第一位不是 '0' ，所以直接返回。 边界情况处理 ： 全零数组 ： nums = [0, 0, 0] 。排序后得到 ["0", "0", "0"] ，拼接为 "000" 。根据规则，我们需要返回 "0" 。一个简单的处理方法是：在最终拼接结果后，检查第一个字符是否为 '0' 。如果是，说明整个字符串都是 '0' ，直接返回 "0" 。 第五步：复杂度分析 时间复杂度 ：O(n log n * k)。其中 n 是数组长度， k 是数组中数字转换为字符串后的最大长度。排序需要进行 O(n log n) 次比较，每次比较（字符串拼接）的时间复杂度是 O(k)。 空间复杂度 ：O(n)。主要用于存储字符串数组。 总结 这个题目巧妙地避开了传统的数值排序，要求我们根据 拼接结果 来定义新的序关系。解题的关键步骤是： 洞察核心 ：发现决定顺序的是 xy 和 yx 的比较结果。 定义规则 ：将数字转为字符串，并基于 s1+s2 与 s2+s1 的比较结果定义排序规则。 实施排序 ：使用任何基于比较的排序算法（如快速排序、归并排序），并传入自定义比较器。 处理细节 ：注意全零数组的特殊情况，返回 "0" 。 它本质上是一种 基于自定义比较规则的排序 ，是排序算法思想的一个非常灵活和实用的应用场景。