Leetcode179. 最大数

2021年5月30日 134点热度 1人点赞 0条评论

题目描述

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

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

示例 1:

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

示例 2:

输入:nums = [3,30,34,5,9]
输出:"9534330"

示例 3:

输入:nums = [1]
输出:"1"

示例 4:

输入:nums = [10]
输出:"10"

提示:

  • $1 \leq nums.length \leq 100$
  • $0 \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 后面。

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

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

具体细节详见下述代码:

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;
}

agedcat_xuanzai

这个人很懒,什么都没留下

文章评论