【LeetCode 中等题】83-最大数

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

示例 1:

输入: [10,2]

输出: 210      

示例 2:

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

输出: 9534330      

说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

备注：python3 sorted取消了对cmp的支持。python3 帮助文档：sorted(iterable，key=None,reverse=False)。key接受一个函数，这个函数只接受一个元素，默认为None；reverse是一个布尔值。如果设置为True，列表元素将被倒序排列，默认为False；着重介绍key的作用原理：key指定一个接收一个参数的函数，这个函数用于从每个元素中提取一个用于比较的关键字。默认值为None 。 

解法1。在Python2里面用Sorted加cmp可实现，但是在Python3中由于取消了内置对象__cmp__方法，所以sorted函数的传入比较函数的cmp参数也取消了。在此先用python2的cmp方法。一般使用key、reverse比cmp更快，因为对每个元素会调用cmp多次，而key和reverse只调用1次

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if not nums:
            return ''
        nums.sort(cmp = lambda x,y: int(str(y)+str(x))-int(str(x)+str(y)))
        return ''.join(str(i) for i in nums) if nums[0] != 0 else '0'

# 这里用sorted也可，直接用map把nums里的元素变成str型
class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if not nums:
            return ''
        arr = sorted(map(str, nums), cmp = lambda x,y: int(y+x) - int(x+y))
        return ''.join(arr) if arr[0] != '0' else '0'           

解法2。python3的解法，手动定义key后面的函数

class Solution(object):
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        LargeNum = ''.join(sorted(map(str, nums), key=LargeNumCompare))
        return '0' if LargeNum[0] == '0' else LargeNum

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

解法2。python3的解法，利用已有的轮子cmp_to_key，其实相当于上一种解法的简化

class Solution:
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        if not nums:
            return ''
        from functools import cmp_to_key
        cmp2key = cmp_to_key(lambda x,y: int(y+x)-int(x+y))
        arr = sorted(map(str, nums), key = cmp2key)
        return ''.join(arr) if arr[0] != '0' else '0'