☆打卡算法☆LeetCode 179. 最大数 算法解析
一、题目
1、算法题目
“给定一个非负整数，重新排列数的顺序使之组成一个最大整数。”
题目链接：
来源：力扣（LeetCode）
2、题目描述
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意： 输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入： nums = [10,2]
输出： "210"示例 2：
输入： nums = [3,30,34,5,9]
输出： "9534330"二、解题
1、思路分析
这道题要求重新排列每个数的顺序组成最大整数，可以逐个比较数组的中数值，将较大的数值放到前面。
比如：[45,56,81,76,123] ，结果:"81765645123"。
但是，数组中有相同数字开头的情况，比如[4,42]和[4,45]:
- 对于[4,42]，比较442>424，需要把4放前面
- 对于[4,45]，比如445<454，需要把45放前面
对于这种在排序前无法确定两个数谁大的情况应该怎么排序的？
这种情况就可以根据不同的排序 结果 来决定两个数的排序关系：
- 如果结果，ab>ba，则需要将a放在b前面
- 如果结果，ab<ba，则需要将b放到a前面
2、代码实现
代码参考：
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
String[] ss = new String[n];
for (int i = 0; i < n; i++) ss[i] = "" + nums[i];
Arrays.sort(ss, (a, b) -> {
String sa = a + b, sb = b + a ;
return sb.compareTo(sa);
});
StringBuilder sb = new StringBuilder();
for (String s : ss) sb.append(s);
int len = sb.length();
int k = 0;
while (k < len - 1 && sb.charAt(k) == '0') k++;
return sb.substring(k);
}
}
image.png
3、时间复杂度
时间复杂度：O(n2)
由于是对String进行排序，当排序对象不是Java中基本数据类型时，不会使用快排，Arrays.sort()底层会使用插入排序，那么时间复杂度就是O(n2)。
空间复杂度：O(n)
其中n是数组的长度。
三、总结
总结来说解题思路就是：
- 转成字符串数组
- 两两比较字符串中的元素的大小
- 以结果为导向，确定哪个元素在前面
- 输出结果
本文参与 腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。
原始发表：2022-08-03，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
