0179. 最大数 #
- 标签:贪心、字符串、排序
- 难度:中等
题目大意 #
描述:给定一个非负整数数组 nums
。
要求:重新排列数组中每个数的顺序,使之将数组中所有数字按顺序拼接起来所组成的整数最大。
说明:
- $1 \le nums.length \le 100$。
- $0 \le nums[i] \le 10^9$。
示例:
- 示例 1:
|
|
- 示例 2:
|
|
解题思路 #
思路 1:排序 #
本质上是给数组进行排序。假设 x
、y
是数组 nums
中的两个元素。如果拼接字符串 x + y < y + x
,则 y > x
。y
应该排在 x
前面。反之,则 y < x
。
按照上述规则,对原数组进行排序即可。这里我们使用了 functools.cmp_to_key
自定义排序函数。
思路 1:代码 #
|
|
思路 1:复杂度分析 #
- 时间复杂度:$O(n^2)$。其中 $n$ 是给定数组
nums
的大小。 - 空间复杂度:$O(n)$。