Leetcode179. 最大数

题目描述

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

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

示例 1：

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

示例 2：

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

示例 3：

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

示例 4：

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

提示：

  • 1≤nums.length≤1001 \leq nums.length \leq 100
  • 0≤nums[i]≤1090 \leq nums[i] \leq 10^9

解题思路

这道题如果数组中的数没有相同数字开头，那么这道题非常好做。直接将整数类型的数组转换为字符串类型的数组，然后直接按字符串比较大小的方式将里面的字符串从大到小排序（比较过程是，首先比较输入数组的每个元素的最高位，最高位相同比较次高位，以此类推），最后依次拼接起来就好。

但是这道题中输入数组包含有相同数字开头的情况，例如 [4,42] 和[4,45]。

对于 [4,42]，比较 442 > 424，需要把 4 放在前面；
对于 [4,45]，比较 445 < 454，需要把 45 放在前面。

因此我们需要比较不同的拼接顺序的结果，进而决定它们在结果中的排列顺序。

如果用暴力的方法去比较，时间复杂度爆炸。我们需要定义一种新的排序比较规则：

对于字符串 a ，和字符串 b ，

​ 如果 a + b > b +a ，那么 a 排在 b 前面；

​ 否则，a 排在 b 后面。

然后套用没有相同数字开头的情况的处理方法，并且用新定义的排序规则就可以解决包含有相同数字开头的情况。

具体的证明过程比较复杂，感兴趣的可以看官方解答。

具体细节详见下述代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
string largestNumber(vector<int>& nums)
{
    if(nums.empty()) return "";
    vector<string>trans;
    for(auto x:nums)
    {
        trans.push_back(to_string(x));
    }
    sort(trans.begin(),trans.end(),[](string& a,string& b)
    {
        return a+b>b+a;
    });
    if(trans[0]=="0") return "0";
    string res="";
    for(auto x:trans)
    {
        res+=x;
    }
    return res;
}