亲宝软件园·资讯

展开

Go java算法最大数

黄丫丫 人气:0

最大数

给定一组非负整数 nums,重新排列每个数的顺序(每个数不可拆分)使之组成一个最大的整数。

注意:输出结果可能非常大,所以你需要返回一个字符串而不是整数。

输入:nums = [10,2]

输出:"210"

输入:nums = [3,30,34,5,9]

输出:"9534330"  

提示:

1 <= nums.length <= 100

0 <= nums[i] <= 109

方法一:排序(java)

要想组成最大的整数,一种直观的想法是把数值大的数放在高位。

于是我们可以比较输入数组的每个元素的最高位,最高位相同的时候比较次高位

以此类推,完成排序,然后把它们拼接起来。这种排序方式对于输入数组 没有相同数字开头 的时候是有效的

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        // 转换成包装类型,以便传入 Comparator 对象(此处为 lambda 表达式)
        Integer[] numsArr = new Integer[n];
        for (int i = 0; i &lt; n; i++) {
            numsArr[i] = nums[i];
        }
        Arrays.sort(numsArr, (x, y) -&gt; {
            long sx = 10, sy = 10;
            while (sx &lt;= x) {
                sx *= 10;
            }
            while (sy &lt;= 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 &lt;= x {
            sx *= 10
        }
        for sy &lt;= y {
            sy *= 10
        }
        return sy*x+y &gt; 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)

加载全部内容

相关教程
猜你喜欢
用户评论