js求数组中全部数字可拼接出的最大整数示例代码

题目描述：

给定一个由非负整数构成的数组，将它们按照字典序排序后拼接成一个整数，求这个整数的最大值。

例如，数组 [3, 30, 34, 5, 9] 可以拼接成数字 9534330，为最大值。

解题思路：

直接将数组按照字典序排序会出现问题，例如对于数组 [3, 30]，按照字典序排序得到 [30, 3]，但是显然正确的排列顺序应该是 [3, 30]，因为拼接后的数字 330 要比 303 大。

所以我们要自定义一种排序规则，排序时比较两个数 a 和 b：

- 如果 a 和 b 拼接起来得到的数字大于 b 和 a 拼接起来得到的数字，那么 a 应该排在 b 的前面；

- 如果 a 和 b 拼接起来得到的数字小于 b 和 a 拼接起来得到的数字，那么 a 应该排在 b 的后面；

- 如果 a 和 b 拼接起来得到的数字相等，那么 a 和 b 相对顺序不变。

这个排序规则是根据题目要求得出的，比较函数的具体实现如下：

function compare(a, b) {

let ab = "" + a + b;

let ba = "" + b + a;

return ba.localeCompare(ab);

}

将数组按照上述规则排序，然后将数组中的所有数拼接起来得到结果。

解题代码：

function largestNumber(nums) {
  nums.sort(compare);
  let result = nums.join('');
  if (result[0] === '0') {
    return '0';
  }
  return result;
}

function compare(a, b) {
  let ab = "" + a + b;
  let ba = "" + b + a;
  return ba.localeCompare(ab);
}

console.log(largestNumber([3, 30, 34, 5, 9])); // "9534330"
console.log(largestNumber([0, 0])); // "0"
console.log(largestNumber([0, 1, 0])); // "110"

完整代码：

/**
 * 求数组中全部数字可拼接出的最大整数
 * @param {number[]} nums
 * @return {string}
 */
function largestNumber(nums) {
  nums.sort(compare);
  let result = nums.join('');
  if (result[0] === '0') {
    return '0';
  }
  return result;
}

/**
 * 比较函数，根据题目要求自定义排序规则
 * @param {number} a
 * @param {number} b
 * @return {number}
 */
function compare(a, b) {
  let ab = "" + a + b;
  let ba = "" + b + a;
  return ba.localeCompare(ab);
}

console.log(largestNumber([3, 30, 34, 5, 9])); // "9534330"
console.log(largestNumber([0, 0])); // "0"
console.log(largestNumber([0, 1, 0])); // "110"

时间复杂度：排序的时间复杂度为 $O(n \log n)$，拼接数组的时间复杂度为 $O(n)$，所以总的时间复杂度为 $O(n \log n)$。

空间复杂度：没有使用额外的空间，所以空间复杂度为 $O(1)$。