P3121. 卡片组成的最大数字

解题思路

注意，本题和 经典题型. 最大数 完全相同。

核心思想

很容易想到，在排序这些数字时，需要把 高位（以个位为低位算起）大的数 尽可能 贪心 地排序到最前面。这样才能尽可能地让整个字符串排序后得到的数字尽可能大。

例如，考虑示例三：

我们自然会想先让 9999 排到最前面，然后是 4589，然后是 41425，最后才是 101。

比较逻辑

这其实是基于以下逻辑：对于两个特定的字符串 x 和 y，它们可以以 x + y 的方式拼接，也可以以 y + x 的方式拼接。显然这两个拼接后的字符串长度相等。在选择排序先后顺序时，我们总是期望能够拼接出 转化为数字之后，数字序更大的那个字符串。

如果把这个思路写成一个函数 compare：

其中 compare(x, y) 的返回值含义如下：

• 返回 -1 表示 x 要排在 y 前面
• 返回 1 表示 y 要排在 x 前面

这是因为 compare 函数的返回值定义了两个元素的相对大小，就像在数值比较时：

• x < y 时返回负值（如 -1），说明 x 应该排在 y 前面
• x > y 时返回正值（如 1），说明 y 应该排在 x 前面
• x == y 时返回 0，说明 x 和 y 相对位置无关紧要

简单来理解：

• compare(x, y) 函数返回 负数（如 -1）时，排序的顺序和传参的顺序一致
• compare(x, y) 函数返回 正数（如 1）时，排序的顺序和传参的顺序相反

Python 实现

在 Python 中，我们可以通过导入 functools 中的 cmp_to_key 函数来结合 compare 函数实现这样的排序。

具体代码如下：

使用 lambda 匿名函数

如果我们把上述 compare() 函数抽象为一个包含两个参数的 lambda 匿名函数，还可以写成这样：

此处的 lambda 匿名函数和 compare() 函数一样，必须包含 x 和 y 两个参数。其返回的结果 int(y + x) - int(x + y) 表示：

• 若 y + x 的拼接结果大于 x + y，则返回一个 正数，所以排序顺序和传参顺序相反，y 要排在 x 前面
• 若 y + x 的拼接结果小于 x + y，则返回一个 负数，所以排序顺序和传参顺序相同，x 要排在 y 前面
• 若 y + x 的拼接结果等于 x + y，则返回 0，x 和 y 的顺序无关紧要

那么也能得到和上述 compare() 函数一样的计算结果。

特别说明

需要特别注意的是，这是在 Python 写法中，极少数无法仅使用 lambda 匿名函数，而必须使用 `cmp_to_key()` 函数来辅助进行排序的题目。

cmp_to_key 的这种排序风格，是 基于两个元素之间的关系 而不是简单的基于单个元素的数字大小、字母顺序或者和自身元素值直接相关的某个指标来进行排序。

而在 C++、Java 等其他主流语言中，cmp_to_key 的这种基于两个元素之间关系的排序风格其实非常常见。

复杂度分析 设 n 为卡片（切割出的字符串）的数量，L 为单个数字字符串的最大长度。

• 时间复杂度：O(n·L·log n)。瓶颈在排序：排序过程需要 O(n log n) 次比较，而这里每一次比较都不是普通的数值比较，而是先把两个字符串拼接成 x+y 与 y+x（长度至多 2L），再逐字符比较大小，单次比较的代价为 O(L)。排序完成后把全部字符串拼接输出为 O(n·L)，不影响总体量级。
• 空间复杂度：O(n·L)，用于储存切割后的字符串数组；每次比较时临时产生的两个拼接字符串各占 O(L)。