LeetCode179—Largest Number-蒲公英云

LeetCode179—Largest Number

你的名字 2022-07-14 15:18 232阅读 0赞

原题

原题链接

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

分析

用数组中的数字组合成最大的数。可以利用string的比较的特性，对于数组中的两个元素a，b来说，在最终的最大字符串中，他们的最终位置只有可能两种情况，XXXaXXXbXX或者是XXXbXXXaXX，也就是说不是a在b前面就是b在a前面，这取决于把a、b组合在一起组成的“数”谁更大。

a和b都是string 类型
如果a+b> b+a 则 a在b前面。

因此我们可以按照这个比较规则将数组进行排序，用STL sort写一个简单的比较函数即可。

代码

bool comp(const string&s1,const string &s2)
{
    return s1+s2>s2+s1;
}//比较函数
class Solution
{
    public:
    string largestNumber(vector<int>& nums)
        {
        vector<string>vec;
        for(int i=0;i<nums.size();++i)
        {
            vec.push_back(std::to_string(nums[i]));
        }
        sort(vec.begin(),vec.end(),comp);
        string res;
        for(int i=0;i < vec.size();++i)
        {
            res+=vec[i];
        }
        //以下代码为了去除前导的0，排除[0,0]这种case
        int j=0;
        while(res[j]=='0'&&res[j+1]=='0')
        {
             res.erase(res.begin());
        }
        return res;
    }
};