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

1. Backtracking

  搜索会超时。

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        if not nums:
            return ''
        res = ['']
        self.dfs(nums, '', res)
        return res[0]
    
    def dfs(self, nums, path, res):
        if not nums or len(nums) == 0:
            if res[0] == '':
                res[0] = path
            elif float(path) > float(res[0]):
                res[0] = path
            return
        
        n = len(nums)
        for i in range(n):
            self.dfs(nums[:i]+nums[i+1:], path+str(nums[i]), res)
# Time Limit Exceeded
# 35/222 cases passed (N/A)
# Testcase
# [1,2,3,4,5,6,7,8,9,0]

2. Sort

  举例子试一下就会发现是直接通过新建一种比较大小的顺序,来讲数据排序就可以了,这里比较大小的方式就是看两个字符换位置连接后比较数值大小。

class compare(str):
    def __lt__(x, y):
        return x+y > y+x

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        # res = ''.join(sorted(map(str, nums), key=lambda x, y: int(x+y)-int(y+x)))
        res = ''.join(sorted([str(v) for v in nums], key=compare))
        return res if res[0]!='0' else '0'
# 222/222 cases passed (36 ms)
# Your runtime beats 93.4 % of python3 submissions
# Your memory usage beats 100 % of python3 submissions (12.9 MB)
# Python 2
class Solution:
    def largestNumber(self, numbers):
        # write code here
        if numbers is None:
            return None
        str_numbers = [str(i) for i in numbers]
        res = sorted(str_numbers, cmp=lambda x, y: cmp(x+y, y+x))
        return ''.join(res)

3. 神操作

class Solution:
    def helper(self,nums,i):
        if int(nums[i+1]+nums[i]) > int(nums[i]+nums[i+1]):
            nums[i], nums[i+1] = nums[i+1],nums[i]
    def largestNumber(self, nums) -> str:
        nums = [str(item) for item in nums]
        nums.sort(reverse=True)
        for j in range(1, len(nums)):
            for i in range(0, len(nums)-j):
                if nums[i+1] in nums[i] and nums[i+1] != nums[i]:
                    self.helper(nums, i)
        return str(int(''.join(nums)))
class Solution:
    def largestNumber(self, nums):
        if set(nums) == {0}:
            return '0'
        nums = list(map(str,nums))
        len_list = list(map(len,nums))
        max_len = max(len_list)
        min_len = min(len_list)
        i = max_len//min_len+1
        
        nums.sort(reverse = True,key=lambda x:x*i)
        return "".join(nums)

References

  1. 179. Largest Number