组成最大数

题目来源于 https://leetcode-cn.com/problems/largest-number/

问题

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例1：

输入: [10,2] 输出: 210

示例2：

输入: [3,30,34,5,9] 输出: 9534330

返回最大数的字符串。

思路

方式是“大”的数放到前面，判断“大”有以下几个情况

1. ‘10’+’5’ < ‘5’+’10’
2. ‘10’+’1’ < ‘1’+’10’

结果就是，’a’ + ‘b’ < ‘b’ + ‘a’ 时，说明 b > a

解法

方法1：

冒泡排序，将“大”的数放到前面。

时间复杂度：\(O({n^2})\)

def largestNumber(self, nums: List[int]) -> str:
        for i in range(len(nums)-1):
            for j in range(i+1,len(nums)):
                if int(str(nums[i])+str(nums[j]))<int(str(nums[j])+str(nums[i])) :
                    nums[i],nums[j]=nums[j],nums[i]

        if nums[0]==0:
            return '0'
        return ''.join(list(map(str,nums)))

方法2：

最优解

时间复杂度：\(O(nlgn)\)，空间复杂度：\(O(n)\)

# 继承str类，并重写比较函数
class LargerNumKey(str):
    def __lt__(self, other):
        return self+other > other+self

class Solution:
    def largestNumber(self, nums):
        largest_num = ''.join(sorted(map(str, nums), key=LargerNumKey))
        # 对于首个数字是0的情况，直接返回0
        return largest_num.lstrip('0') or '0'

go 版本

func largestNumber(nums []int) string {
        var s Numlist
        for i := 0; i < len(nums); i++ {
            numstr := strconv.Itoa(nums[i])
            s = append(s, numstr)
        }
        sort.Sort(s)
        if s[0] == "0" {
            return "0"
        }
        var ans string
        for i := 0; i < len(s); i++{
            ans += s[i]
        }
        return ans
}

type Numlist []string

func (n Numlist) Len() int      { return len(n) }
func (n Numlist) Swap(i, j int) { n[i], n[j] = n[j], n[i] }
func (n Numlist) Less(i, j int) bool {
        return n[i]+n[j]> n[j]+n[i]
}