剑指 Offer 45. 把数组排成最小的数 #
- 标签:贪心、字符串、排序
- 难度:中等
题目大意 #
描述:给定一个非负整数数组 nums
。
要求:将数组中的数字拼接起来排成一个数,打印能拼接出的所有数字中的最小的一个。
说明:
- $0 < nums.length \le 100$。
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数。
- 拼接起来的数字可能会有前导
0
,最后结果不需要去掉前导0
。
示例:
|
|
解题思路 #
思路 1:自定义排序 #
本质上是给数组进行排序。假设 x
、y
是数组 nums
中的两个元素。则排序的判断规则如下所示:
- 如果拼接字符串
x + y > y + x
,则x
大于y
,y
应该排在x
前面,从而使拼接起来的数字尽可能的小。 - 反之,如果拼接字符串
x + y < y + x
,则x
小于y
,x
应该排在y
前面,从而使拼接起来的数字尽可能的小。
按照上述规则,对原数组进行排序。这里使用了 functools.cmp_to_key
自定义排序函数。
思路 1:自定义排序代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n \times \log_2n)$。排序算法的时间复杂度为 $O(n \times \log_2n)$。
- 空间复杂度:$O(1)$。