高考加油!
带好证件!

剑指 Offer 45. 把数组排成最小的数

2021-06-09 大聪明 0评论 19 0喜欢

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

示例 1:

输入: [10,2]
输出: "102"
示例 2:

输入: [3,30,34,5,9]
输出: "3033459"

提示:

0 < nums.length <= 100
说明:

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

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

考察点:排序

排序规则:

if stra + strb > strb + stra: stra < strb

else: stra > strb

也就是说,两个字符串a和b,如果a+b拼接后得到的int数大于b+a拼接后得到的int数,那么b就应该排在a的前边。

[3,30,34,5,9] ‘3’ + ‘30’ = ‘330’ > ’303‘ = ‘30’ + ‘3’ 所以相对位置 ...30...3....

经典的排序算法有很多,这里我选择了一个快速排序算法,比起冒泡之类的相对时间会快一点。

class Solution(object):
    def minNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        def quick_sort(low, high):
            if low < high:
                i = low
                j = high
                key = arr[i]
                while i < j:
                    while i < j and arr[j] + key >= key + arr[j]:
                        j -= 1
                    if i < j:
                        arr[i] = arr[j]
                        i += 1
                    while i < j and arr[i] + key < key + arr[i]:
                        i += 1
                    if i < j:
                        arr[j] = arr[i]
                        j -= 1
                    arr[i] = key
                quick_sort(low, i-1)
                quick_sort(i+1, high)
        arr = [str(i) for i in nums]
        quick_sort(0, len(arr)-1)
        return ''.join(arr)


# s = Solution()
# res = s.minNumber([3,30,34,5,9])
# print(res)

发表评论 取消回复

电子邮件地址不会被公开。

请输入正确格式的qq邮箱
请输入以http或https开头的URL,格式如:https://libo_sober.top