【python】Leetcode每日一题-最大数

【python】Leetcode每日一题-最大数

【题目描述】

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

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

示例1：

输入：nums = [10,2]
输出："210"

示例2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例3：

输入：nums = [1]
输出："1"

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 109

【分析】

• 分治法的思想

  感觉这题寻常思路（单纯比大小）会有很多坑，由此想到更契合这题的大小比较方式\(s1+s2>s2+s1=>s1+s2\)，即对两个数经过这样的比较后即可确定两者前后关系，如\([4,42]\)，比较 \(442 > 424\)，需要把 \(4\) 放在前面。如此而来，只需要比较\(C_n^m\)即可。这时可以用到递归分治的思路，即数组第一个数与其他数的位置关系，再递归分治比这个数小的以及比这个数大的其他数即可。

  递归式：\(parse(left) + str(nums[0]) + parse(right)\)

• 代码

class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        m = self.parse(nums)
        if m[0] == "0":
            return "0"
        return m
        
    def parse(self, nums):
        if len(nums) == 0:
            return ""
        if len(nums) == 1:
            return str(nums[0])
        left = []
        right = []
        for i in range(1, len(nums)):
            if int(str(nums[i]) + str(nums[0])) > int(str(nums[0]) + str(nums[i])):
                left.append(nums[i])
            else:
                right.append(nums[i])
        return self.parse(left) + str(nums[0]) + self.parse(right)

• 看了官方及一些题解，使用的基本上都是lambda表达式，即自定义比较式。

  官方：
  var largestNumber = function(nums) {
      nums.sort((x, y) => {		//这一段即是比较str(x)+str(y)<?>str(y)+str(x)的lambda表达式
          let sx = 10, sy = 10;
          while (sx <= x) {
              sx *= 10;		//sx表示比x大一个数量级的值，如，x:24，sx:100
          }
          while (sy <= y) {
              sy *= 10;
          }
          return '' + (sx * y + x) - ('' + (sy * x + y));
      })
      if (nums[0] === 0) {
          return '0';
      }
      return nums.join('');
  };
  

  python同理：
  from functools import cmp_to_key
  class Solution:
      def largestNumber(self, nums: List[int]) -> str:
          nums.sort(key=cmp_to_key(lambda x,y: int(str(y)+str(x)) - int(str(x)+str(y))))
          ans = ''.join([str(num) for num in nums])
          return str(int(ans))