“给定一个非负整数,重新排列数的顺序使之组成一个最大整数。”
题目链接:
来源:力扣(LeetCode)
给定一组非负整数 nums
,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意: 输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入: nums = [10,2]
输出: "210"
示例 2:
输入: nums = [3,30,34,5,9]
输出: "9534330"
这道题要求重新排列每个数的顺序组成最大整数,可以逐个比较数组的中数值,将较大的数值放到前面。
比如:[45,56,81,76,123] ,结果:"81765645123"。
但是,数组中有相同数字开头的情况,比如[4,42]和[4,45]:
对于这种在排序前无法确定两个数谁大的情况应该怎么排序的?
这种情况就可以根据不同的排序 结果 来决定两个数的排序关系:
代码参考:
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);
}
}
时间复杂度:O(n2)
由于是对String进行排序,当排序对象不是Java中基本数据类型时,不会使用快排,Arrays.sort()底层会使用插入排序,那么时间复杂度就是O(n2)。
空间复杂度:O(n)
其中n是数组的长度。
总结来说解题思路就是: