LeetCode 题解 | 179. 最大数

大家好，欢迎来到IT知识分享网。

力扣 179. 最大数（点击查看题目）

题目描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

示例 2:

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

​

解决方案

自定义排序：

想法

为了构建最大数字，我们希望越高位的数字越大越好。

算法

首先，我们将每个整数变成字符串。然后进行排序。

如果仅按降序排序，有相同的开头数字的时候会出现问题。比方说，样例 2 按降序排序得到的数字是 ，然而交换 3 和 30 的位置可以得到正确答案 。因此，每一对数在排序的比较过程中，我们比较两种连接顺序哪一种更好。我们可以证明这样的做法是正确的：

假设（不是一般性），某一对整数 a 和 b，我们的比较结果是 a 应该在 b 前面，这意味着 a ⌢ b > b ⌢ a，其中 ⌢ 表示连接。如果排序结果是错的，说明存在一个 c，b 在 c 前面且 c 在 a 的前面。这产生了矛盾，因为 a ⌢ b > b ⌢ a 和 b ⌢ c > c ⌢ b 意味着 a ⌢ c > c ⌢ a。换言之，我们的自定义比较方法保证了传递性，所以这样子排序是对的。

一旦数组排好了序，最“重要”的数字会在最前面。有一个需要注意的情况是如果数组只包含 0，我们直接返回结果 0 即可。否则，我们用排好序的数组形成一个字符串并返回。

Java 实现

Python 实现

复杂度分析

• 时间复杂度：O(nlgn)

尽管我们在比较函数中做了一些额外的工作，但是这只是一个常数因子。所以总的时间复杂度是由排序决定的，在 Python 和 Java 中都是 O(nlgn)。

• 空间复杂度：O(n)

这里，我们使用了 O(n) 的额外空间去保存 nums 的副本。尽管我们就地进行了一些额外的工作，但最后返回的数组需要 O(n) 的空间。因此，需要的额外空间与 nums 大小成线性关系。

本文作者：力扣

声明：本文归“力扣”版权所有，如需转载请联系。