0179-Largest Number( 最大数)

末蓝、 2022-09-01 13:51 29阅读 0赞

> 这个系列算是出于个人兴趣开的一个新坑吧，最近看到同学刷LeetCode算法题，就想写写那些可以一行Python代码写出来的题目，因此本专栏的文章的解题方式效率不做保证，只为追求“一行的浪漫”。

## 题目 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob3VjaGVuMTk5OA_size_16_color_FFFFFF_t_70_pic_center]

## 题解 ##

简单解释一下题目，给定一个**非负**数组`nums`，将这些数字拼接到一起形成一个大数，由于该数很大，需要以字符串的形式输出。**本题难度为Medium。**

## 代码 ##

这道题的题解思路在于，你不可能遍历所有的组合情况然后选出最大的那种，这样一定会TLE的。可以考虑从字符串的角度来理解，就是**两个数字字符`a`和`b`是拼接成`a+b`还是`b+a`更大在Python中可以依靠等长字符串直接比大小得出结果**（因此，如果输入`x`和`y`，且`x+y < y+x`那么此时`x`应该在后面，因此为了契合默认的升序排序，这里输出一个负数即可）。那么只要对整个字符串列表按照这个规则进行降序排序（内部其实是逐个比较的过程），那么排序的结果其实就是最大数构成的顺序，将他们顺次拼接到一起即可。**这里需要注意的是，因为输入非负，所以可能是全0，这时候输出会是`000`这种格式，这里因为一行不便判断，所以用int函数检查后再转为str输出。**

class Solution:
        def largestNumber(self, nums: List[int]) -> str:
            return str(int("".join(sorted(map(str, nums), key = functools.cmp_to_key(lambda x,y: 1 if x+y < y+x else -1)))))

从下面的提交反馈来看，效率不是很高（时间复杂度为 O ( N ∗ l o g ( N ) ) O(N\* log(N)) O(N∗log(N))，空间复杂度为 O ( N ) O(N) O(N)），大家也应当考虑高效的方法，部分题目的高效解法可以参考[我的仓库源码][Link 1]。

![在这里插入图片描述][54c1d76a8a704a9eafc51248b4142855.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3pob3VjaGVuMTk5OA_size_16_color_FFFFFF_t_70_pic_center]: /images/20220829/4142a5094fd042cfaf52961fb7f239d6.png
[Link 1]: https://github.com/luanshiyinyang/LeetCode
[54c1d76a8a704a9eafc51248b4142855.png_pic_center]: /images/20220829/15aaaea65ef94e51ab951425c3c50ea8.png