[数据结构与算法]leetcode 179 自定义一个字符比较函数

179. 最大数

难度中等1035收藏分享切换为英文接收动态反馈

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

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

示例 1：

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

示例?2：

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

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 109

通过次数179,007提交次数434,715

题解：这种题目属于用瞪眼题目，也就是一看就知道怎么实现可以最优，但是写程序往往不是很好实现。我的思路是先将数字转为字符串，然后就转为了字符串比较排序的问题，默认的sort函数提供两种方式来排序，从小到大，或者从大到小，这里就需要自己定义一个排序函数，总的方向是从大到小，但是大小如何判断呢，比如“9”和“987”，显然这道题目里面，应该是“9”大于“987”，如果使用模式的排序方式，就会发过来。曾经想到了桶排序，但是会陷入沉思，无法出来。最后看到了一个神奇的定义方式：

bool compare(const string& s1,const string& s2){
    string str1=s1+s2;
    string str2=s2+s1;
    return str1>str2;//自定义比较函数，返回大的字符串
}

看到这个豁然开朗，这正是我需要的大小判断方式。

于是代码跃然纸上：

class Solution {
    static bool compare(const string& s1,const string& s2){
    string str1=s1+s2;
    string str2=s2+s1;
    return str1>str2;//自定义比较函数，返回大的字符串
    }
public:
    string largestNumber(vector<int>& nums) {
        vector<string> temp(nums.size());
        for(int i=0;i<nums.size();i++)
        {
            temp[i]=to_string(nums[i]);
        }
        //sort(temp.rbegin(), temp.rend());
        sort(temp.begin(),temp.end(),compare);
        string res;
        for(int i=0;i<temp.size();i++)
        {
            res+=temp[i];
        }
        string res2="";
        for(int i=0;i<res.size();i++)
        {
            if(res[i]=='0' && res2=="")
            {
                continue;
            }
            else
            {
                res2+=res[i];
            }
        }
        return res2==""?"0":res2;
    }
};

以上是正确写法：如果compare函数不加static声明，则会产生如下错误。

?

执行结果：

通过

显示详情

添加备注

执行用时：4 ms, 在所有?C++?提交中击败了90.91%的用户

内存消耗：11 MB, 在所有?C++?提交中击败了41.49%的用户

通过测试用例：230?/?230

还有遇到一个问题就是，测试用例为["0","0"]的情况，需要处理开头的0，所以代码里面出现了res2的结果返回。