力扣179:最大数【C++】

题目分析

原题:

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

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

分析:

这道题题意不难理解,暴力解法的思路也不难想,但是实现起来其实是比较困难的,而且时间复杂度远远达不到要求。因此要考虑能够减小时间复杂度的逻辑。同时要注意,返回的是字符串。

思路分析

我们可以先拿两个数{5,34}举例子,这两个数在不拆分的情况下,可以组成的整数个数为两个,534和345,显然534要更大,因此要测试用例为这两个数,则答案就是”534“。

那么我们该如何用代码实现呢?大家可以观察,534和345这两个数字是怎么得到的,是不是像是用了一种特殊的加法,而字符串与数字类型不同,谁在前,加出来的结果是有区别的。因此,这种加法的原理跟字符串的拼接一样。所以自然而然想到把所有的数字转换为字符串进行拼接,这是解题的精髓之一。

返回这个例子{5,34},假如数据不变,而顺序变了呢,即{34,5}。我们能够判断出来,这个整数是534,那么我们如何将这个整数以字符串形式返回呢?

可能小伙伴觉得,这不简单嘛?但是这是在只有两个数字的情况下,如果整个字符串数组包括很多元素,我们要按什么原则将这个整数拼接起来呢?没错,呼之欲出,排序。

排序原则的构造也是解题的精髓之一。大家可以这么思考,如果一个字符串拼接容器中任何一个其他的字符串所得到的整数,都大于其他的字符串拼接它,那么这个字符串就应该放在首位,因为其他任何一个字符串放在首位都不如它大。因此排序的原则应当是:字符串1+字符串2>字符串2+字符串1(其实小于也可以,无非就是最后for循环的顺序从头递增还是从尾递减,不过还是建议大于)。

下面是我所写的代码实现:

class Solution {
public:
    static bool compare(string a,string b){//排序规则
        return a+b>b+a;
    }
    string largestNumber(vector<int>& nums) {
        string str;//用于作返回值
        vector<string>str_nums;//用于装转换string类型后nums容器中的data
        for(auto i:nums){//C++11新特性
            str_nums.push_back(to_string(i));//to_string函数用于将i变量对应的data转换为string类型
        }
        sort(str_nums.begin(),str_nums.end(),compare);//排序
        if(str_nums[0]=="0"){
            return "0";//避免输入为{0,0,0}全是0的情况下输出很多个0,此时输出1个0即可
        }
        for(auto j:str_nums){
            str+=j;/字符串从头到尾拼接
        }
        return str;
    }
};

关于排序规则compare函数,为什么设置为静态成员函数,请大家看我的博客《Debug:reference to non-static member function must be called》,里面有详细的解释。