Sword finger offer 45. arrange the array into the smallest number

subject

Enter an array of nonnegative integers , Put all the numbers in the array together to form a number , Print the smallest of all the numbers that can be spliced .

Example 1:

 Input : [10,2]
 Output : "102"

Example 2:

 Input : [3,30,34,5,9]
 Output : "3033459"

Tips :
0 < nums.length <= 100
explain :
The output can be very large , So you need to return a string instead of an integer
The stitched numbers may have a lead 0, The final result does not need to remove the lead 0

Ideas

• Convert to character array
• The idea of sorting

Program

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        nums_str = [str(num) for num in nums]

        def quick_sort(l,r):
            if l >= r: return 

            i,j = l, r
            while i < j :
                while i < j and nums_str[j] + nums_str[l] >= nums_str[l] + nums_str[j]: 
                    j = j -1
                while i < j and nums_str[i] + nums_str[l] <= nums_str[l] + nums_str[i] : 
                    i = i +  1
                nums_str[i],nums_str[j] = nums_str[j],nums_str[i]

            nums_str[i],nums_str[l]= nums_str[l],nums_str[i]
            quick_sort(l,i -1)
            quick_sort(i+1,r)

        quick_sort(0,len(nums_str)-1)

        return ''.join(nums_str)