Description:

Given a list of non negative integers, arrange them such that they form the largest number.

Example 1:

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

Example 2:

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

Note: The result may be very large, so you need to return a string instead of an integer.

Solutions:

野路子

NOTE: 把每个数字都延长到最长数字的长度，第一次延长用最后一位来重复，sort之后发现有3个case没过不去。主要问题是[84,847]，应该顺序是84(4) 847而不是847 84(4)。然后有了第二次postfix的修改，采用上一位的首数字来延长。再sort一次就好了。

还要注意用str(int(ret))去0

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        max_l = len(str(max(nums)))
        
        def helper(num,postfix=None):
            string = str(num)
            if not postfix:
                modified = string + string[-1]*(max_l - len(string))
            else:
                modified = string + postfix*(max_l - len(string))
            return [string,int(modified)]
        
        new_ls = [helper(n) for n in nums]
        new_ls.sort(reverse = True,key = lambda x : x[1])
        
        
        for i in range(1,len(new_ls)):
            new_ls[i][1] = helper(int(new_ls[i][0]),new_ls[i-1][0][0])[1]
            
            
        new_ls.sort(reverse = True,key = lambda x : x[1])
        
        ret = ""
        for i in new_ls:
            ret += i[0]
        return str(int(ret))

Runtime: 48 ms, faster than 53.62% of Python3 online submissions for Largest Number.
Memory Usage: 13.9 MB, less than 5.63% of Python3 online submissions for Largest Number.

Better solution:

inspired by https://www.cnblogs.com/grandyang/p/4225047.html

class Number:
    def __init__(self,n):
        self.val = n
        self.str = str(n)
    def __lt__(self,other):
        return int(self.str+other.str) < int(other.str+self.str)
    
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        new_ls = [Number(n) for n in nums]
        new_ls.sort(reverse = True)
        return str(int("".join([n.str for n in new_ls])))

Runtime: 48 ms, faster than 53.62% of Python3 online submissions for Largest Number.
Memory Usage: 13.9 MB, less than 5.63% of Python3 online submissions for Largest Number.

sample 36 ms submission

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        return ''.join(sorted(list(map(str, nums)), \
                          key=cmp_to_key(lambda x, y: -1 if x + y > y + x else 1))).lstrip('0') or '0'

Adapt my code by using cmp_to_key

NOTE:

• The usage of cmp_to_key
• strings could be compared by not being transformed into int first
• The usage of lstrip
• The usage of or in return （语法糖）

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        nums = [str(n) for n in nums]
        cmp = lambda a,b: 1 if a+b > b+a else \
                          0 if a+b == b+a else -1
        nums.sort(reverse=True,key = cmp_to_key(cmp))
        
        return "".join(nums).lstrip("0") or "0"

Runtime: 40 ms, faster than 93.62% of Python3 online submissions for Largest Number.
Memory Usage: 13.9 MB, less than 5.63% of Python3 online submissions for Largest Number.