题目

标题和出处

标题：最大数

出处：179. 最大数

难度

6 级

题目描述

要求

给定一组非负整数nums \texttt{nums}nums，重新排列每个数的顺序使之组成一个最大的整数，并返回该最大的整数。

由于结果可能非常大，所以返回一个字符串而不是整数。

示例

示例 1：

输入：nums = [10,2] \texttt{nums = [10,2]}nums = [10,2]
输出："210" \texttt{"210"}"210"

示例 2：

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

数据范围

• 1 ≤ nums.length ≤ 100 \texttt{1} \le \texttt{nums.length} \le \texttt{100}1≤nums.length≤100
• 0 ≤ nums[i] ≤ 10 9 \texttt{0} \le \texttt{nums[i]} \le \texttt{10}^\texttt{9}0≤nums[i]≤109

解法

思路和算法

为了将给定数组中的非负整数拼接成最大整数，需要从字典序的角度考虑整数的相对顺序。

一种直观的排序方法是将每个整数按照字典序排序。该排序方法的结果并不总是正确的，例如对于数组[ 12 , 121 ] [12, 121][12,121]，该排序方法得到的结果是12112 1211212112，但是最大整数是12121 1212112121。

正确的排序方法是根据两个整数的拼接结果排序。对于整数a aa和b bb，排序方法如下。

• 当a = b a = ba=b时，可以按照任意顺序排序。

• 当a ≠ b a \ne ba=b时，考虑两种拼接的结果，a aa在左、b bb在右的拼接结果是a b ‾ \overline{ab}ab，b bb在左、a aa在右的拼接结果是b a ‾ \overline{ba}ba。如果a b ‾ > b a ‾ \overline{ab} > \overline{ba}ab>ba则排序结果是a aa在前、b bb在后，如果a b ‾ < b a ‾ \overline{ab} < \overline{ba}ab<ba则排序结果是b bb在前、a aa在后。

根据两个整数的拼接结果排序，排序之后将所有整数拼接成的整数即为最大的整数。

对于结果整数，需要注意去除前导零。

证明

根据两个整数的拼接结果排序的策略为贪心策略，需要证明贪心策略的正确性，即数组中的所有数拼接成最大数的充分必要条件是根据拼接结果排序。

需要分别证明必要性和充分性。

必要性

如果一种排列顺序中存在两个相邻的整数a aa和b bb，满足a aa在左、b bb在右且a b ‾ < b a ‾ \overline{ab} < \overline{ba}ab<ba，则将a aa和b bb的位置交换之后可以得到更大的数。因此当数组中的所有数拼接成最大数时，数组中的元素一定满足根据两个整数的拼接结果排序的顺序，必要性得到证明。

充分性

两个整数的拼接结果决定的排序顺序为一种二元关系，需要证明该二元关系满足完全性和传递性。

完全性的含义是，对于任意两个整数a aa和b bb，可以唯一地确定两个整数的顺序。两个整数的顺序可以根据两个整数拼接后的结果唯一地确定，因此满足完全性。

传递性的含义是，对于任意三个整数a aa、b bb和c cc，如果满足a aa在b bb的前面，b bb在c cc的前面，则必有a aa在c cc的前面。

对于非负整数x xx，定义函数f ( x ) f(x)f(x)表示大于x xx的最小的10 1010的整数次幂，f ( x ) f(x)f(x)的表达式如下。

f ( x ) = { 10 , x = 0 10 ⌊ log ⁡ 10 x ⌋ + 1 , x > 0 f(x) = \begin{cases} 10, & x = 0 \\ 10^{\lfloor \log_{10} x \rfloor + 1}, & x > 0 \end{cases}f(x)={10,10⌊log10​x⌋+1,​x=0x>0​

则有a b ‾ = a × f ( b ) + b \overline{ab} = a \times f(b) + bab=a×f(b)+b。

当满足a aa在b bb的前面且b bb在c cc的前面时，a b ‾ ≥ b a ‾ \overline{ab} \ge \overline{ba}ab≥ba，b c ‾ ≥ c b ‾ \overline{bc} \ge \overline{cb}bc≥cb。

将函数f ff代入得到a × f ( b ) + b ≥ b × f ( a ) + a a \times f(b) + b \ge b \times f(a) + aa×f(b)+b≥b×f(a)+a，b × f ( c ) + c ≥ c × f ( b ) + b b \times f(c) + c \ge c \times f(b) + bb×f(c)+c≥c×f(b)+b。

经过移项整理得到a × ( f ( b ) − 1 ) ≥ b × ( f ( a ) − 1 ) a \times (f(b) - 1) \ge b \times (f(a) - 1)a×(f(b)−1)≥b×(f(a)−1)，b × ( f ( c ) − 1 ) ≥ c × ( f ( b ) − 1 ) b \times (f(c) - 1) \ge c \times (f(b) - 1)b×(f(c)−1)≥c×(f(b)−1)。

由于两个不等式的不等号两边的值都是非负数，因此将两个不等式的不等号两边分别相乘得到a × b × ( f ( b ) − 1 ) × ( f ( c ) − 1 ) ≥ b × c × ( f ( a ) − 1 ) × ( f ( b ) − 1 ) a \times b \times (f(b) - 1) \times (f(c) - 1) \ge b \times c \times (f(a) - 1) \times (f(b) - 1)a×b×(f(b)−1)×(f(c)−1)≥b×c×(f(a)−1)×(f(b)−1)，整理得到b × ( f ( b ) − 1 ) × ( a × ( f ( c ) − 1 ) − c × ( f ( a ) − 1 ) ) ≥ 0 b \times (f(b) - 1) \times (a \times (f(c) - 1) - c \times (f(a) - 1)) \ge 0b×(f(b)−1)×(a×(f(c)−1)−c×(f(a)−1))≥0。由于f ( b ) ≥ 10 f(b) \ge 10f(b)≥10，因此f ( b ) > 0 f(b) > 0f(b)>0，分别考虑b = 0 b = 0b=0和b > 0 b > 0b>0的情况。

• 当b = 0 b = 0b=0时，f ( b ) = 10 f(b) = 10f(b)=10，代入a b ‾ ≥ b a ‾ \overline{ab} \ge \overline{ba}ab≥ba，b c ‾ ≥ c b ‾ \overline{bc} \ge \overline{cb}bc≥cb，得到a × 10 + 0 ≥ 0 × f ( a ) + a a \times 10 + 0 \ge 0 \times f(a) + aa×10+0≥0×f(a)+a，0 × f ( c ) + c ≥ c × 10 + 0 0 \times f(c) + c \ge c \times 10 + 00×f(c)+c≥c×10+0，化简得到10 a ≥ a 10a \ge a10a≥a，c ≥ 10 c c \ge 10cc≥10c，因此a aa可以是任意非负整数，c = 0 c = 0c=0，此时a c ‾ ≥ c a ‾ \overline{ac} \ge \overline{ca}ac≥ca。

• 当b > 0 b > 0b>0时，为了使b × ( f ( b ) − 1 ) × ( a × ( f ( c ) − 1 ) − c × ( f ( a ) − 1 ) ) ≥ 0 b \times (f(b) - 1) \times (a \times (f(c) - 1) - c \times (f(a) - 1)) \ge 0b×(f(b)−1)×(a×(f(c)−1)−c×(f(a)−1))≥0成立，应满足a × ( f ( c ) − 1 ) − c × ( f ( a ) − 1 ) ≥ 0 a \times (f(c) - 1) - c \times (f(a) - 1) \ge 0a×(f(c)−1)−c×(f(a)−1)≥0，经过移项得到a × f ( c ) + c ≥ c × f ( a ) + a a \times f(c) + c \ge c \times f(a) + aa×f(c)+c≥c×f(a)+a，等价于a c ‾ ≥ c a ‾ \overline{ac} \ge \overline{ca}ac≥ca。

因此无论是b = 0 b = 0b=0还是b > 0 b > 0b>0，都有a c ‾ ≥ c a ‾ \overline{ac} \ge \overline{ca}ac≥ca。传递性成立。

由于贪心策略下的二元关系满足完全性和传递性，因此充分性得到证明。

代码

classSolution{publicStringlargestNumber(int[]nums){intlength=nums.length;String[]array=newString[length];for(inti=0;i<length;i++){array[i]=String.valueOf(nums[i]);}Arrays.sort(array,(a,b)->b.concat(a).compareTo(a.concat(b)));StringBuffersb=newStringBuffer();for(inti=0;i<length;i++){if(sb.isEmpty()&&"0".equals(array[i])){continue;}sb.append(array[i]);}returnsb.isEmpty()?"0":sb.toString();}}

复杂度分析

• 时间复杂度：O ( n log ⁡ n ) O(n \log n)O(nlogn)，其中n nn是数组nums \textit{nums}nums的长度。创建长度为n nn的字符串数组存储每个整数的字符串表示需要O ( n ) O(n)O(n)的时间，将字符串数组排序需要O ( n log ⁡ n ) O(n \log n)O(nlogn)的时间，排序之后遍历字符串数组得到结果需要O ( n ) O(n)O(n)的时间，因此时间复杂度是O ( n log ⁡ n ) O(n \log n)O(nlogn)。由于数组中的每个非负整数都不超过10 9 10^9109，因此每个整数的长度不超过10 1010，将每个整数的字符串表示的长度视为常数。

• 空间复杂度：O ( n ) O(n)O(n)，其中n nn是字符串nums \textit{nums}nums的长度。需要创建长度为n nn的字符串数组存储每个整数的字符串表示，由于数组中的每个非负整数都不超过10 9 10^9109，因此每个整数的长度不超过10 1010，将每个整数的字符串表示的长度视为常数。