题目179

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

样例输入

输入：nums = [3,30,34,5,9]

输出：”9534330”

问题分析

核心问题在于组合后数字的排序方法。

最简单粗暴的想法当然是第一个数字越大的，越要往前排。但是题目中nums给的数字长度又不一样长。于是去以一个长度为2的nums为例：[3,30]，可以发现，当较长的num（例子中长度为2的数字30）第二位比第一位小时，则较短num（例子中长度为1的数字3）排在前面好，否则较长数字排在前面好，例如[45,4]。

根据这种特性，就需要先按第一位数字分类；在第一位数字相同的组里，根据第二位数字再次分类。以此类推，直到每类中只有一个数字结束。但是如果出现一些长度很长，前缀又相同的数字，这个比较方式就会非常漫长。

而题解告诉我们，这个问题核心是一个数字排序问题。只需要将前面分析出来的排序方法，通过一个比较函数来展现，然后直接让快排函数来实现具体的排序流程即可。就快排的实现方法，这里就涉及两个trick来优化，一类是无限小数法，一类是测试法。

1. 无限小数法的思路，就是逐位分析，利用无限循环小数来将数字最左端对齐。

   通过构造循环小数，比如k=123是三位数，可以通过log10方法或计算字符串长度方法求出长度L=3。之后用如下方法构造循环小数： \(\frac{123}{10^3-1} =\frac{123}{999} =0.123123123\) 例如，当a=3，b=32。将其转换为循环小数后：x=0.333333，y=0.323232。

   此时 x > y ,会发现x中从前往后总会出现一个数大于y中对应位置的数，所以字符串 str(a)+str(b) 中从前往后也会出现一个数大于str(b)+str(a) 中对应位置的数，使得str(a)+str(b)>str(b)+str(a)

2. 测试法的思路就是，逐个拼接一下，如何a+b>b+a，则a应放置于b之前。即可表示为a>b。

题解

class Solution(object):
    def largestNumber(self, nums):
        def fun(x):
            if x==0:return 0
            L=int(math.log10(x))+1
            return x/(10**L-1)
        nums.sort(key=fun,reverse=True)
        nums=list(map(str,nums))
        return str(int("".join(nums)))