三个月算法进阶--day73

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def quicksort(start, end):
            if start >= end:
                return
            if start + 1 == end:
                if int(strs[start] + strs[end]) > int(strs[end] + strs[start]):
                    strs[start], strs[end] = strs[end], strs[start]
                return
            pivot = strs[start]
            tmp1 = start
            tmp2 = end
            start += 1
            while end > start:
                if int(strs[start] + pivot) > int(pivot + strs[start]):
                    strs[start], strs[end] = strs[end], strs[start]
                    end -= 1
                    continue
                if int(strs[end] + pivot) < int(pivot + strs[end]):
                    strs[start], strs[end] = strs[end], strs[start]
                    start += 1
                    continue
                start += 1
                end -= 1
            if int(strs[end] + pivot) > int(pivot + strs[end]):
                end -= 1
            strs[end], strs[tmp1] = pivot, strs[end]
            quicksort(tmp1, end-1)
            quicksort(end+1, tmp2)
        strs = [str(i) for i in nums]
        quicksort(0, len(strs)-1)
        return ''.join(strs)

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

class Solution:
    def minNumber(self, nums: List[int]) -> str:
        def sort_rule(x, y):
            a, b = x + y, y + x
            if a > b: return 1
            elif a < b: return -1
            else: return 0
        
        strs = [str(num) for num in nums]
        strs.sort(key = functools.cmp_to_key(sort_rule))
        return ''.join(strs)