这篇文章主要介绍LeetCode如何把数组排成最小的数,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
题目描述
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
-
0 < nums.length <= 100 -
输出结果可能非常大,所以你需要返回一个字符串而不是整数 -
拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
题目样例
示例
-
输入: [10,2]
-
输出: "102"
-
输入: [3,30,34,5,9]
-
输出: "3033459"
题目思考
-
怎么定义最小?
解决方案
思路
-
分析题目, 要使得拼接起来的数字最小, 只有当各个拼接元素按照从小到大拼接起来才可以 -
而这里的从小到大拼接, 不是指按照数字本身顺序或者字典序从小到大拼接 -
举个例子, 90 和 902 的拼接结果应该是 90290, 但是 90 不管是数字还是字典序都小于 902 -
那如何定义哪个数字作为拼接后的第一个数字呢? -
假如这个数字和任意其他数字拼接起来, 都小于将两个数字互换后拼接的结果, 那么显然这个数字就应该放在首位 -
到这里就知道了, 我们应该自定义一个排序方法, 对于两个数字 a 和 b 而言, 比较
str(a)+str(b)
与
str(b)+str(a)
的大小关系, 然后对整个列表排序后组成一个字符串即可 -
下面的代码使用两种方案实现, 一种是快速排序, 一种是语言内置排序, 供大家参考
复杂度
-
时间复杂度
O(NlogN)
-
排序的时间复杂度 -
空间复杂度
O(N)
-
使用了额外的字符串数组
代码
方案 1 – 自定义快速排序
class Solution:
def minNumber(self, nums: List[int]) -> str:
# 使用map将原数组的数字转成字符串
nums = list(map(str, nums))
def quicksort(l, r):
# 经典快速排序实现
if l >= r:
return
pivot = nums[l]
i, j = l, r
while i < j:
# 只需要把这里改成自定义的排序方法即可
while i < j and nums[j] + pivot >= pivot + nums[j]:
j -= 1
nums[i] = nums[j]
# 只需要把这里改成自定义的排序方法即可
while i < j and nums[i] + pivot <= pivot + nums[i]:
i += 1
nums[j] = nums[i]
nums[i] = pivot
quicksort(l, i - 1)
quicksort(i + 1, r)
quicksort(0, len(nums) - 1)
return ''.join(nums)
方案 2 – 自定义内置排序
class Solution:
def minNumber(self, nums: List[int]) -> str:
class compare(str):
def __lt__(self, x):
return self + x < x + self
# 使用python内置sorted的key, 传入一个重载__lt__的类, 自定义排序
return ''.join(sorted(map(str, nums), key=compare))
以上是“LeetCode如何把数组排成最小的数”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
原创文章,作者:745907710,如若转载,请注明出处:https://blog.ytso.com/223477.html