难度: Medium
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]输出："210"
示例 2：
输入：nums = [3,30,34,5,9]输出："9534330"
提示：
1 <= nums.length <= 1000 <= nums[i] <= 109
Submission
运行时间: 20 ms
内存: 15.9 MB
class Solution:
def largestNumber(self,nums) -> str:
def compare(x,y):
a,b=x+y,y+x
if a>b:
return 1
elif a<b:
return -1
else:
return 0
nums = [str(i) for i in nums]
nums.sort(key=cmp_to_key(compare),reverse=True)
if nums[0] == '0':
return '0'
return ''.join(nums)
Explain
这个题解的思路是将数组中的数字转换为字符串，然后通过自定义的比较函数对字符串进行排序。比较函数的规则是，比较两个字符串 x 和 y 拼接后的大小，如果 x+y > y+x，则 x 排在前面；如果 x+y < y+x，则 y 排在前面；如果相等，则顺序不变。排序后，将字符串数组拼接起来即可得到最大数。如果排序后的第一个元素为 '0'，说明所有数字都为 0，直接返回 '0'。
时间复杂度: O(nlogn)
空间复杂度: O(n)
class Solution:
def largestNumber(self, nums) -> str:
def compare(x, y):
# 比较两个字符串拼接后的大小
a, b = x + y, y + x
if a > b:
return 1
elif a < b:
return -1
else:
return 0
# 将整数转换为字符串
nums = [str(i) for i in nums]
# 使用自定义比较函数对字符串进行降序排序
nums.sort(key=cmp_to_key(compare), reverse=True)
# 如果排序后的第一个元素为 '0'，说明所有数字都为 0，直接返回 '0'
if nums[0] == '0':
return '0'
# 将字符串数组拼接成最大数
return ''.join(nums)
Explore
这种比较方式基于构造最大数的目标。当我们比较两个数字x和y时，将它们视为字符串后，拼接成两种组合x+y和y+x，就可以比较这两种组合的字典序大小。如果x+y的字典序大于y+x，意味着把x放在y前可以构造出更大的数，因此在排序函数中x应该排在y前面。这种比较方法直接关联到最终拼接成的数字的最大性，从而有效地帮助我们达到将数组构造成最大数的目的。
通过将每个数字转化为字符串，并比较拼接后的结果（x+y与y+x），可以自然地解决长度不同的问题。这种比较方法本质上是考虑了所有可能的排列组合，确保无论数字的原始长度如何，都能按照能形成的最大数值的顺序进行排序。例如，数字'3'和'34'比较，'334'与'343'的字典序明显显示'343'更大，因此'34'应该在'3'前面，这保证了比较的准确性。
字符串的排序性能确实会受到字符串长度的影响。在这种情况下，每次比较都涉及到字符串的拼接和比较，因此比较操作的时间复杂度与字符串的长度成正比。如果处理的数据量大且字符串长度长，这将导致排序操作变得较为耗时。排序的总体时间复杂度受到比较次数（通常是O(n log n)）和每次比较的复杂度（与字符串长度相关）的影响。
这种返回值设计符合Python内置排序函数的要求，其中比较函数需要返回一个可以明确比较结果的整数。返回1表示第一个参数应该位于第二个参数之后，返回-1表示第一个参数应该位于第二个参数之前，返回0表示两者相等。这与许多其他编程语言中的比较逻辑类似，使得这种比较可以直接用于Python的排序函数中，实现自定义的排序逻辑。这种设计简化了排序代码的编写，使开发者可以更容易地控制排序行为。