目录

0179:最大数(★)

力扣第 179 题

题目

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

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

示例 1:

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

示例 2:

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

提示:

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

相似问题:

分析

  • 首先想到按字典序降序拼接,但是某些情况并不适用

    • 例如 [3,30,34,5,9] 的字典序降序为 [9,5,34,30,3],但正确的顺序应该是 [9,5,34,3,30]。
  • 因此需要重新定义优先顺序。这里有个巧妙的想法:

    • 只要 $\overline{AB}>\overline{BA}$,就认为 A 的优先级更高,应该排在前面。
  • 直觉告诉我们这样很可能是正确的,不过需要证明一下。 采用反证法:

    • 假设最大结果 res 中存在 $\overline{AB}>\overline{BA}$ 但 B 排在 A 的前面
      • 显然 B 和 A 不可能是相邻的,否则直接交换就得到更大的结果了
      • 故res 是 $\overline{…BCA…}$ 的形式
      • 同理,应该有 $\overline{BC} \geq \overline{CB},\overline{CA} \geq \overline{AC}$,否则交换下就得到更大的结果
    • 设 A、B、C 对应的字符串长度分别为 x、y、z,那么: $$\overline{BC} \geq \overline{CB}, \overline{CA} \geq \overline{AC}$$ $$\Rarr \begin{cases} B * 10^z + C \geq C * 10^y + B \\ C * 10^x + A \geq A * 10^z + C \end{cases} $$ $$ \Rarr \begin{cases} B * (10^z-1) \geq C * (10^y-1) \\ C * (10^x-1) \geq A * (10^z-1) \end{cases}$$ $$ \Rarr B * C * (10^z-1) * (10^x-1) \geq C * A * (10^y-1) * (10^z-1) $$ $$ \Rarr B * (10^x-1) \geq A * (10^y-1) $$ $$ \Rarr B * 10^x + A \geq A * 10^y + B $$ $$ \Rarr \overline{BA} \geq \overline{AB} ,矛盾。 $$
  • 故对于任意 $\overline{AB}>\overline{BA}$,应该将 A 排在 B 的前面。

解答

1
2
3
4
5
class Solution:
    def largestNumber(self, nums: List[int]) -> str:
        cmp = lambda x,y: 1 if x+y<y+x else -1 if x+y>y+x else 0
        res = ''.join(sorted(map(str, nums), key=cmp_to_key(cmp)))
        return res.lstrip('0') or '0'

40 ms