179 Largest Number

problem definition

input [10,2]

output “210”

 

my solution

def largestNumber(self, nums: [int]) -> str:
    if not any(nums):
        return "0"

    def compare(x, y):
        a = x + y
        b = y + x
        if a > b:
            return 1
        elif a < b:
            return -1
        return 0

    def search(val, nums):
        l = 0
        r = len(nums) - 1

        while l <= r:
            m = (l + r)//2
            ret = compare(val, nums[m])
            if ret == 0:
                return m
            if ret > 0:
                l = m + 1
            else:
                r = m - 1

        return l

    nums = [str(i) for i in nums]
    res = []
    for num in nums:
        idx = search(num, res)
        res.insert(idx, num)

    return ''.join(res[::-1])

O(nlogn)