Go&java算法之最大數示例詳解

Posted on by

最大數

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

註意：輸出結果可能非常大，所以你需要返回一個字符串而不是整數。

  • 示例 1：

輸入：nums = [10,2]

輸出："210"

  • 示例 2：

輸入：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)

以上就是Go&amp;java算法之最大數示例詳解的詳細內容，更多關於Go java算法最大數的資料請關註WalkonNet其它相關文章！

推薦閱讀：