179. 最大数.md

179. 最大数

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

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

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

示例 3：

输入：nums = [1]
输出："1"

示例 4：

输入：nums = [10]
输出："10"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

思路

先将数字转换为字符串，然后用 ab 和 ba做比较按照 从大到小 排序然后再拼接，最后去掉前面的 0

代码

/**
 * @param {number[]} nums
 * @return {string}
 */
var largestNumber = function(nums) {
  nums.sort((a, b) => calcMax(a, b))
  let str = nums.reduce((prev, cur) => prev + cur, '');
  let i = 0;
  for(;i < str.length - 1;) {
    if (str[i] == '0') {
      i ++
    } else {
      break;
    }
  }

  return str.substring(i)
};

function calcMax(a, b) {
  let strA = a.toString(), strB = b.toString();
  let ab = strA + strB, ba = strB + strA
  let maxLen = ab.length;
  for(let i = 0; i < maxLen;) {
    let curA = ab[i], curB = ba[i]
    if (curA - curB > 0) {
      return -1
    } else if (curA == curB) {
      i ++
    } else {
      return 1
    }
  }
  return 0
}

复杂度分析

时间复杂度 $O(NlogN)$

空间复杂度 $O(N)$