leetcode-179. 最大数

179. 最大数

直接按数值大小排序行不通。例如输入 [3,30,34,5,9]，虽然 30 大于 9，但拼成 930 比 309 大。普通字典序也不合适：比较“3”和“30”时，字典序会把“30”排在前面，可实际拼接时，330 又比 303 大。

可以先比较局部的拼接结果。对于两个数字字符串 A、B，只有 A+B 和 B+A 两种顺序；如果 $A+B>B+A$，就把 A 放在 B 前面。这里比较的是拼接结果，不是原数字的大小。推广到 A、B、C 时，如果比较结果要求 A 在 B、C 前面，而 C 在 B 前面，最终顺序就是 ACB。

因此，先把所有数字转成字符串，再按上述拼接规则排序，最后把排序结果连接起来。

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

Python 的 sort 接收 key 函数，而 key 一次只接收一个元素。这里的规则需要同时比较两个元素，所以先定义 compare，再用 functools 中的 cmp_to_key 将比较函数转换为 sort 可用的排序键。

返回值决定顺序：compare(x, y) 小于 0 时，x 排在 y 前面。因此，当 x+y > y+x 时返回负值，让拼接结果更大的顺序在前；其余情况返回正值，采用相反的排列顺序。

最后还要处理全零输入。例如 [0,0,0] 排序后会拼成“000”，应返回“0”。按上述规则排好序后，如果第一个字符串为“0”，说明没有其他非零数字，直接返回“0”即可。