难度: Medium
闯关游戏需要破解一组密码，闯关组给出的有关密码的线索是：
passwordpassword 中所有元素拼接后得到的最小的一个数请编写一个程序返回这个密码。
示例 1:
输入: password = [15, 8, 7] 输出: "1578"
示例 2:
输入: password = [0, 3, 30, 34, 5, 9] 输出: "03033459"
提示:
0 < password.length <= 100说明:
运行时间: 48 ms
内存: 14.8 MB
import functools
class Solution:
def minNumber(self, nums: List[int]) -> str:
def sort_rule(x, y):
a, b = x + y, y + x
if a > b:
return 1
elif a < b:
return -1
else:
return 0
nums_2_strs = [str(num) for num in nums]
nums_2_strs.sort(key=functools.cmp_to_key(sort_rule))
return ''.join(nums_2_strs)
这道题要求从一个整数数组中通过全排列得到一个拼接后的最小数。题解中采用了自定义排序策略来解决这个问题。首先，将整数数组转换为字符串数组，以便于处理数字的拼接。接着，定义了一个排序规则 sort_rule，该规则比较两个字符串 x 和 y 拼接后的结果 x+y 和 y+x，来决定 x 和 y 在结果列表中的顺序。这样的比较保证了全局最小的拼接顺序可以被找到。最后，利用 functools.cmp_to_key 将 sort_rule 转换为排序函数，对字符串数组进行排序，并将排序后的数组拼接成一个字符串返回。
时间复杂度: O(n log n * m)
空间复杂度: O(n)
import functools
class Solution:
def minNumber(self, nums: List[int]) -> str:
# 自定义排序规则
def sort_rule(x, y):
a, b = x + y, y + x # 拼接两种可能的字符串
if a > b:
return 1 # a > b 时，x 应该在 y 后面
elif a < b:
return -1 # a < b 时，x 应该在 y 前面
else:
return 0 # a == b 时，顺序无关紧要
# 将数字转换为字符串，以便进行字符串比较
nums_2_strs = [str(num) for num in nums]
# 使用自定义排序规则进行排序
nums_2_strs.sort(key=functools.cmp_to_key(sort_rule))
# 将排序后的字符串数组拼接成一个字符串并返回
return ''.join(nums_2_strs)
通过比较`x+y`和`y+x`，这种方法实际上是在比较两个数在不同顺序拼接时产生的字典序大小。字典序较小的拼接方式意味着在最终的拼接数中会更小。这种比较确保了如果`x`放在`y`前面可以得到更小的拼接数，那么`x`就应该在`y`前面。这样的全局性质通过局部的比较被保持，从而确保整个数组按此规则排序后，得到的拼接字符串是所有可能拼接结果中最小的。
当`x`和`y`拼接后相等，即`x+y == y+x`时，这表明无论`x`和`y`的顺序如何，拼接结果都是相同的。这种情况确实可以发生，特别是当`x`和`y`相等时，或者它们是彼此的前缀时。返回0表示在排序过程中，`x`与`y`的相对位置可以是任意的，这不会影响最终的拼接结果。因此，这种情况不会对最终的排序结果产生负面影响。
将整数数组转换为字符串数组确实会有一定的性能影响，主要表现在内存使用和转换时间上。每个整数转换为字符串需要分配新的内存空间，并且转换过程涉及到数位的处理，这在数组长度非常大时会增加计算量。然而，这种转换是解决问题的关键，因为它允许我们使用字符串比较来决定数字的最优排序。尽管有这些性能考虑，但通常这种方法是可行的，特别是考虑到它解决问题的有效性。
`functools.cmp_to_key`方法允许开发者通过比较函数（接受两个参数并返回比较结果）来定义排序规则，这为复杂的排序提供了很大的灵活性。优势在于可以处理那些不直接支持比较操作的复杂数据结构或排序规则。缺点是，这种方法可能比直接使用基于比较的排序操作更慢，因为它需要在每次比较时调用比较函数，并且通过`cmp_to_key`转换的过程增加了额外的调用开销。尽管如此，对于某些特定的、需要自定义排序逻辑的情况，使用这种方法是非常合适的。