Leetcode 179. 最大数 / python实现

题目

解题思路

从示例中可以发现就是让我们对数组进行某种排序。

很直观的可以发现，相当于对数的每一位进行比较，如果前面位数都相同，数A某一位大于数B的相同位数就表示A应该放在数组的前面，eg：9大于30。

难点在于判断只有一位不同的数字，eg：3和30，就采用直接拼接两者，看哪一种组合更大，就知道谁应该在前面，继而将这种思路推广到全部数字的比较。

代码实现

class Solution:
    def largestNumber(self, nums) -> str:
        nums = list(map(str, nums))
        for i in range(len(nums)-1):
            for j in range(i+1, len(nums)):
                # eg 3和30,330 > 303所以不用换位置
                if int(nums[i]+nums[j]) <= int(nums[j]+nums[i]):
                    nums[i], nums[j] = nums[j], nums[i]
        # 处理前置的0
        while nums and nums[0] == '0':
            nums.pop(0)
        return "".join(nums) if nums else '0'

使用自带的排序函数，利用functools的cmp_to_key

from functools import cmp_to_key
class Solution:
    def largestNumber(self, nums) -> str:
        nums = list(map(str, nums))
        # 匿名函数的返回值应为1（应该交换位置，将b放到前面）或-1或0（两者相等）
        nums = sorted(nums, key=cmp_to_key(lambda a, b: 1 if int(b+a) > int(a+b) else -1))
        while nums and nums[0] == '0':
            nums.pop(0)
        return "".join(nums) if nums else '0'