179. 最大数
题目描述
输入一组非负整数 nums。把这些数按某种顺序首尾拼接成一个整数，每个数作为整体使用，不能拆开。
求能拼出的最大整数。结果可能超出整数范围，因此以字符串返回。
示例 1
输入：nums = [10,2] 输出："210"
解释："2" + "10" = "210" 比 "102" 大。
示例 2
输入：nums = [3,30,34,5,9] 输出："9534330"
解释：按 9、5、34、3、30 的顺序拼接得到最大值。
数据范围
1 <= nums.length <= 1000 <= nums[i] <= 10^9
解题思路
把数字转成字符串，定义比较规则：若 a+b > b+a，则 a 应排在 b 前面。按这个规则排序后直接拼接。这个比较具有传递性，所以排序结果就是全局最优；若排序后第一个是 "0"，说明全是 0，返回 "0"。
为什么正确
排好序的序列中任意相邻两项 a、b 都满足 a+b ≥ b+a，交换任何相邻两项都不会让结果更大。
复杂度分析
时间 O(n log n · L)，L 为数字的最大位数；空间 O(n·L)。
易错点
不能直接按字典序降序："30" 的字典序大于 "3"，但 3 应该排在 30 前面。全是 0 时要返回 "0" 而不是 "000"。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def largestNumber(self, nums: List[int]) -> str:
strs = [str(x) for x in nums]
def cmp(a, b):
if a + b > b + a:
return -1
if a + b < b + a:
return 1
return 0
strs.sort(key=cmp_to_key(cmp))
if strs[0] == '0':
return '0'
return ''.join(strs)class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) strs[i] = String.valueOf(nums[i]);
Comparator<String> cmp = (a, b) -> {
if ((a + b).compareTo(b + a) > 0)
return -1;
if ((a + b).compareTo(b + a) < 0)
return 1;
return 0;
};
Arrays.sort(strs, cmp);
if (strs[0].equals("0"))
return "0";
StringBuilder sb = new StringBuilder();
for (String s : strs) sb.append(s);
return sb.toString();
}
}class Solution {
public:
string largestNumber(vector<int>& nums) {
vector<string> strs;
for (int x : nums) strs.push_back(to_string(x));
auto cmp = [](const string& a, const string& b) {
if (a + b > b + a)
return -1;
if (a + b < b + a)
return 1;
return 0;
};
sort(strs.begin(), strs.end(), [&](const string& a, const string& b) { return cmp(a, b) < 0; });
if (strs[0] == "0")
return "0";
string ans;
for (auto& s : strs) ans += s;
return ans;
}
};func largestNumber(nums []int) string {
strs := make([]string, len(nums))
for i, x := range nums {
strs[i] = strconv.Itoa(x)
}
cmp := func(a, b string) int {
if a+b > b+a {
return -1
}
if a+b < b+a {
return 1
}
return 0
}
sort.Slice(strs, func(i, j int) bool {
return cmp(strs[i], strs[j]) < 0
})
if strs[0] == "0" {
return "0"
}
return strings.Join(strs, "")
}var largestNumber = function(nums) {
const strs = nums.map(String);
strs.sort((a, b) => {
if (a + b > b + a)
return -1;
if (a + b < b + a)
return 1;
return 0;
});
if (strs[0] === '0')
return '0';
return strs.join('');
};function largestNumber(nums: number[]): string {
const strs = nums.map(String);
strs.sort((a: string, b: string): number => {
if (a + b > b + a)
return -1;
if (a + b < b + a)
return 1;
return 0;
});
if (strs[0] === '0')
return '0';
return strs.join('');
}