Go&java算法之最大数示例详解

最大数

给定一组非负整数 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)

来源：https://juejin.cn/post/7131371861677932552