最大数
方法一:排序(java)
方法一:排序(go)
最大数给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。
注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。
示例 1:
输入:nums = [10,2]
输出:"210"
示例 2:
输入:nums = [3,30,34,5,9]
输出:"9534330"
提示:
方法一:排序(java)1 <= nums.length <= 100
0 <= nums[i] <= 109
要想组成最大的整数,一种直观的想法是把数值大的数放在高位。
于是我们可以比较输入数组的每个元素的最高位,最高位相同的时候比较次高位
以此类推,完成排序,然后把它们拼接起来。这种排序方式对于输入数组 没有相同数字开头 的时候是有效的
class Solution {
public String largestNumber(int[] nums) {
int n = nums.length;
// 转换成包装类型,以便传入 Comparator 对象(此处为 lambda 表达式)
Integer[] numsArr = new Integer[n];
for (int i = 0; i < n; i++) {
numsArr[i] = nums[i];
}
Arrays.sort(numsArr, (x, y) -> {
long sx = 10, sy = 10;
while (sx <= x) {
sx *= 10;
}
while (sy <= y) {
sy *= 10;
}
return (int) (-sy * x - y + sx * y + x);
});
if (numsArr[0] == 0) {
return "0";
}
StringBuilder ret = new StringBuilder();
for (int num : numsArr) {
ret.append(num);
}
return ret.toString();
}
}
时间复杂度:O(nlognlogm)
空间复杂度:O(logn)
方法一:排序(go)具体的方法思路已经在上文中表述,详情请看上文内容。
1.核心为插入排序
2.比大小的函数,相加的两种string结果,然后比较各位大小。
3.将排序的结果累加
func largestNumber(nums []int) string {
sort.Slice(nums, func(i, j int) bool {
x, y := nums[i], nums[j]
sx, sy := 10, 10
for sx <= x {
sx *= 10
}
for sy <= y {
sy *= 10
}
return sy*x+y > sx*y+x
})
if nums[0] == 0 {
return "0"
}
ans := []byte{}
for _, x := range nums {
ans = append(ans, strconv.Itoa(x)...)
}
return string(ans)
}
时间复杂度:O(nlognlogm)
空间复杂度:O(logn)
以上就是Go&java算法之最大数示例详解的详细内容,更多关于Go java算法最大数的资料请关注易知道(ezd.cc)其它相关文章!