温馨提示×

温馨提示×

您好,登录后才能下订单哦!

密码登录×
登录注册×
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》

LeetCode如何把数组排成最小的数

发布时间:2021-12-15 13:47:31 来源:亿速云 阅读:164 作者:小新 栏目:大数据

这篇文章主要介绍LeetCode如何把数组排成最小的数,文中介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们一定要看完!


题目描述

输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。

  • 0 < nums.length <= 100
  • 输出结果可能非常大,所以你需要返回一个字符串而不是整数
  • 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
         

题目样例

         

示例

  • 输入: [10,2]

  • 输出: "102"

  • 输入: [3,30,34,5,9]

  • 输出: "3033459"

         

题目思考

  1. 怎么定义最小?
         

解决方案

         

思路

  • 分析题目, 要使得拼接起来的数字最小, 只有当各个拼接元素按照从小到大拼接起来才可以
  • 而这里的从小到大拼接, 不是指按照数字本身顺序或者字典序从小到大拼接
  • 举个例子, 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如何把数组排成最小的数”这篇文章的所有内容,感谢各位的阅读!希望分享的内容对大家有帮助,更多相关知识,欢迎关注亿速云行业资讯频道!

向AI问一下细节

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

AI