[Leetcode 179] 最大数

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
示例 2:
notion image

解法:贪心(推荐)

我们希望把一组数字排成“拼接后最大”的字符串。
关键点在于:我们无法直接按数值大小排序。
如:虽然 3 < 30,但 “330” > “303”, 3 应该排在前。
也就是说,数字本身的大小和拼接后的大小不是一个概念。
题目本质是:
给任意两个数字 x、y,我们要决定 x 在前还是 y 在前,让拼出来的整体更大。
于是我们把 x 和 y 都转成字符串 sxsy,比较:sx + sysy + sx 谁大,谁就应该排在前面。
虽然数字本身的大小不可以直接用于比较,但是拼接得到的字符串可以直接比较。
因为拼接后的长度总是相等的,所以字符串比较等价于数字比较。
比如 "210" > "102" 和 210 > 102是等价的。
这是一个全局正确的贪心规则。只要能比较任意两个元素,就能用普通排序排出全局最优解,然后把排好序的字符串拼起来就是最大数。
另外,如果排完以后第一个是 "0",那结果只能是 "0"(全部都是 0)。
复杂度
  • 时间:
    • 排序:O(n log n) 比较:O(k)(字符串长度) 总体:O(n log n · k)
  • 空间复杂度:O(n · k) 存储字符串
上一篇
[Leetcode 171] Excel 列名转换为数字
下一篇
[Leetcode 200] 岛屿数量