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

剑指 Offer 45. 把数组排成最小的数https://leetcode.cn/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

首先讲解快速排序

快速排序算法_愈努力俞幸运的博客-CSDN博客https://blog.csdn.net/qq_37891604/article/details/125902608?spm=1001.2014.3001.5501那么，对于这道题，只需把排序规则加到快速排序中

此题求拼接起来的最小数字，本质上是一个排序问题。设数组 numsnums 中任意两数字的字符串为 x和 y ，则规定 排序判断规则 为：

若拼接字符串 x + y > y + x ，则 x应在y右边 ；
反之，若 x + y < y + x ，则 x应在y左边 ；
 

class Solution:
    def minNumber(self, nums):
        def qsort(l,r):
            if l>=r: return
            i,j,key=l,r,strs[l]
            while i<j:
                while i<j and strs[j]+key>=key+strs[j]:
                    j-=1
                strs[i],strs[j]=strs[j],strs[i]
                while strs[i]+key<key+strs[i]:
                    i+=1
                if i>=j:break
                strs[i], strs[j] = strs[j], strs[i]
            qsort(l, j-1)
            qsort(j+1, r)
        strs=[str(i) for i in nums]
        qsort(0,len(strs)-1)
        return ''.join(strs)