LeetCode 179. 最大数

1. 解题思路

题目给出一个非负整数数组，要求将所有数字按照某种顺序排列，再拼接成一个尽可能大的整数，最后以字符串形式返回。

最容易想到的方法就是将数组从大到小排序，再依次拼接。

但仔细想想，这样真的能得到最大的结果吗？

例如：

纯文本
nums = [3, 30, 34, 5, 9]

如果按照数字本身的大小排序，显然不一定正确。

虽然 30 大于 9，但把它们拼接起来：

纯文本
9 + 30 = 930
30 + 9 = 309

显然，930 比 309 更大，因此 9 应该排在 30 前面。

那么，直接将数字转换成字符串，再按照字典序从大到小排序呢？

这样也不行。

例如比较 "3" 和 "30"，按照普通字典序降序排列，"30" 会排在 "3" 前面。

但实际拼接后：

纯文本
"3" + "30" = "330"
"30" + "3" = "303"

显然，330 > 303，所以 "3" 才应该排在前面。

通过这两个例子可以发现：这道题不能只比较数字本身的大小，而应该比较它们拼接之后的结果。

2. 自定义排序规则

假设现在有两个数字字符串 A 和 B。

它们只有两种拼接顺序：

  • A + B
  • B + A

既然我们要得到尽可能大的结果，那么只需要比较这两种拼接方式。

如果：

A+B>B+AA+B>B+A

就应该将 A 排在 B 前面。

反之，则将 B 排在前面。

例如：

纯文本
A = "3"
B = "30"

A + B = "330"
B + A = "303"

由于 "330" > "303"，因此 "3" 应该排在 "30" 前面。

同样的规则也可以用于更多数字。

假设有三个字符串 A、B、C，通过两两比较发现：

  • A 应该排在 B 前面。
  • A 应该排在 C 前面。
  • C 应该排在 B 前面。

那么最终顺序就是 ACB。

这样，我们就可以利用排序算法，根据两个元素的拼接结果决定它们的先后顺序。

整体步骤也就明确了：

  1. 将数组中的所有整数转换成字符串。
  2. 定义自定义比较函数，比较 x + y 和 y + x。
  3. 根据比较结果对字符串数组进行排序。
  4. 将排序后的字符串依次拼接，得到最终答案。

3. Python 实现

Python
from functools import cmp_to_key


class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        num_strs = list(map(str, nums))

        def compare(x, y):
            if x + y > y + x:
                return -1
            return 1

        num_strs.sort(key=cmp_to_key(compare))
        res = "".join(num_strs)
        if num_strs[0] == "0":
            return "0"
        return res

4. cmp_to_key 的作用

这里有一个需要注意的地方：Python 的 sort() 接收的是 key 参数，而不是直接接收两个元素进行比较的函数。

通常情况下，key 函数只需要根据单个元素生成排序依据。

但这道题不一样。

我们需要同时拿到两个字符串，比较 x + y 和 y + x，才能确定它们的先后顺序。

因此，可以先定义一个比较函数 compare(x, y)，再使用 functools 模块中的 cmp_to_key()，将它转换成 sort() 可以使用的排序键。

比较函数的返回值含义如下：

  • 小于 0：x 应该排在 y 前面。
  • 大于 0：x 应该排在 y 后面。
  • 等于 0：两个元素在当前比较规则下没有先后之分。

所以，当 x + y > y + x 时，返回 -1，让 x 排在前面。

反过来，如果 x + y < y + x，就应该返回正数，让 y 排在前面。

当两种拼接结果相等时，比较函数应该返回 0。原代码没有单独处理相等的情况，这一点可以进一步完善。

5. 处理全零的特殊情况

最后还需要考虑一个特殊情况：如果数组中的所有数字都是 0，应该如何处理？

例如：

纯文本
nums = [0, 0, 0]

如果直接将排序后的字符串拼接，就会得到：

纯文本
"000"

但题目要求返回的是数字的字符串表示，因此正确答案应该是：

纯文本
"0"

这里不需要专门遍历一遍数组来判断是否全部为零。

因为按照前面的排序规则，如果排序后的第一个字符串就是 "0"，说明数组中不存在其他非零数字。

因此，可以直接判断：

Python
if num_strs[0] == "0":
    return "0"

否则，正常返回拼接后的字符串即可。

6. 复杂度分析

假设数组中有 n 个整数，每个数字转换成字符串后的最大长度为 m。

排序通常需要进行 O(nlog⁡n)O(n\log n) 次比较，而每次比较都需要拼接并比较两个字符串，开销与字符串长度有关。

因此，整体时间复杂度可以表示为：

O(nmlog⁡n)O(nm\log n)

如果把题目中整数的最大位数视为常数，则可以简化为 O(nlog⁡n)O(n\log n)。

空间方面，需要额外保存转换后的字符串及排序过程中的辅助数据。

这道题最关键的地方，是将排序依据从数字本身的大小，改成两个数字不同拼接顺序的大小。

只要确定了这个比较规则，就可以交给排序算法处理，而不需要自己枚举所有排列方式。

谢谢你读到这里。 ✧