最大数

如何用排序拼出最大数？

• 比较规则: 对相邻两数 a、b, 比较拼接串 ab 与 ba;
• ab > ba 时 a 应排在 b 前面, 否则 b 排在前面;
• 字符串比较按逐字符编码顺序进行, 相当于比较拼接后的数值大小;
• 该比较满足传递性, 可直接作为 sort 的比较器;
• 若排序后首位为 0, 说明全部元素是 0, 结果统一返回 "0";

最大数如何实现？

function largestNumber(nums: number[]): string {
  nums.sort((a, b) => (`${a}${b}` < `${b}${a}` ? 1 : -1));
  if (nums[0] === 0) return "0";
  return nums.join("");
}

最大数的复杂度是多少？

• 时间复杂度: O(n log n × a), a 为一次字符串比较的代价;
• 空间复杂度: O(n), 拼接串与结果字符串;