这篇文章主要介绍LeetCode如何把数组排成最小的数,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
输入: [10,2]
输出: "102"
输入: [3,30,34,5,9]
输出: "3033459"
str(a)+str(b)
与
str(b)+str(a)
的大小关系, 然后对整个列表排序后组成一个字符串即可O(NlogN)
O(N)
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)
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如何把数组排成最小的数”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。