Go&java算法之最大數(shù)示例詳解

更新時(shí)間：2022年08月16日 11:20:25 作者：黃丫丫

這篇文章主要為大家介紹了Go&java算法之最大數(shù)示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪

最大數(shù)

給定一組非負(fù)整數(shù) nums，重新排列每個(gè)數(shù)的順序（每個(gè)數(shù)不可拆分）使之組成一個(gè)最大的整數(shù)。

注意：輸出結(jié)果可能非常大，所以你需要返回一個(gè)字符串而不是整數(shù)。

示例 1：

輸入：nums = [10,2]

輸出："210"

示例 2：

輸入：nums = [3,30,34,5,9]

輸出："9534330"

提示：

1 <= nums.length <= 100

0 <= nums[i] <= 109

方法一：排序（java）

要想組成最大的整數(shù)，一種直觀的想法是把數(shù)值大的數(shù)放在高位。

于是我們可以比較輸入數(shù)組的每個(gè)元素的最高位，最高位相同的時(shí)候比較次高位

以此類推，完成排序，然后把它們拼接起來。這種排序方式對(duì)于輸入數(shù)組沒有相同數(shù)字開頭的時(shí)候是有效的

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        // 轉(zhuǎn)換成包裝類型，以便傳入 Comparator 對(duì)象（此處為 lambda 表達(dá)式）
        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();
    }
}

時(shí)間復(fù)雜度：O(nlognlogm)

空間復(fù)雜度：O(logn)

方法一：排序（go）

具體的方法思路已經(jīng)在上文中表述，詳情請(qǐng)看上文內(nèi)容。

1.核心為插入排序

2.比大小的函數(shù)，相加的兩種string結(jié)果，然后比較各位大小。

3.將排序的結(jié)果累加

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)
}

時(shí)間復(fù)雜度：O(nlognlogm)

空間復(fù)雜度：O(logn)

以上就是Go&java算法之最大數(shù)示例詳解的詳細(xì)內(nèi)容，更多關(guān)于Go java算法最大數(shù)的資料請(qǐng)關(guān)注腳本之家其它相關(guān)文章！

您可能感興趣的文章: