Skip to content

Files

Latest commit

8de5761 · Jul 2, 2020

History

History
61 lines (53 loc) · 2.14 KB

179. Largest Number.md

File metadata and controls

61 lines (53 loc) · 2.14 KB

思路

题目给定一个数组,让我们对其合理排序使得拼接成数尽可能大。所以这题其实就是一个排序题。 问题是排序的规则的定义。

给定两个数n1和n2,那么谁排在前面呢?我们可以先将其转换成字符串a和b,判断一下a+b和b+a谁大就可以了。

注意sort自定义的比较函数必须是静态函数。

因为:非静态成员函数是依赖于具体对象的,而std::sort这类函数是全局的,因此无法在sort中调用非静态成员函数。 静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问,无须创建任何对象实例就可以访问。同时静态成员函数不可以调用类的非静态成员。

C++

class Solution {
private:
    // 必须是静态函数
    static bool comp(const string &a, const string &b){
        return a + b > b + a;
    }
public:
    string largestNumber(vector<int>& nums) {
        vector<string>nums_str;
        for(auto &n: nums)
            nums_str.push_back(to_string(n)); // 先将所有数转换成字符串
        
        sort(nums_str.begin(), nums_str.end(), comp);
        string res = "";
        for(auto &n: nums_str)
            res += n;
        
        int i = 0;
        while(i < res.size() && res[i] == '0') i++; // 前导0
        return i == res.size() ? "0": res.substr(i, res.size() - i);
    }
};

也可以将自定义函数直接写在sort函数里:

class Solution {
public:
    string largestNumber(vector<int>& nums) {
        vector<string>nums_str;
        for(auto &n: nums)
            nums_str.push_back(to_string(n)); // 先将所有数转换成字符串
        
        sort(nums_str.begin(), nums_str.end(), 
             [](const string &a, const string &b){
                 return a + b > b + a;
             }
        );
        string res = "";
        for(auto &n: nums_str)
            res += n;
        
        int i = 0;
        while(i < res.size() && res[i] == '0') i++; // 前导0
        return i == res.size() ? "0": res.substr(i, res.size() - i);
    }
};