179. Largest Number

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.

给出一个数组，要求用数组中的数字来组成一个新数字，并且这个新数字是所有可能中最大的一个。

这道题如果可以对数组中的数字进行调整，那么就很简单了，对大于等于10的数字进行分割，之后将分割后得到的各位数字加入数组，小于10的数字也加入这个数组，之后将数组从大到小排序，转化成字符串即可。

然而这道题并不允许我们调整字符串，所以我们得转换思路。

问题的关键在于如何比较任意两个数字的大小:

1. 如果是两个个位数，则直接比较即可。
2. 如果其中有一个超过10的数字，比如23和9，则在这道题的逻辑中，应该是9>23
3. 如果某个数的前半部分和另一个数完全相同，则看该数剩下的那部分和另一个数的大小关系，如6532和65比较时，65是大于6532的，因为65大于32。
4. …………

由此可见，如果要细分各种情况，会十分复杂，所以在参阅了讨论区之后我得到了这样一种思路。

要判断任意两个数的大小关系，可以将其转换为字符串之后，对其进行正反两次拼接，比较获得的两个字符串的大小关系即可，本题中用到的比较函数的代码如下:

bool compTwoString(string& s1,string& s2){
        return s1+s2>s2+s1;
}

这个函数会作为参数被传给sort函数，但现在有一个问题，如果就这样对compTwoString进行定义的话，编译器会报错，提示invalid use of non-static member function，这是什么原因呢？

因为我们使用的std::sort()函数是一个全局函数，而我们定义的比较函数是一个非静态成员函数，非静态成员函数是依赖于具体对象的，所以我们无法在全局函数中调用非静态成员函数，那么我们在声明函数时就需要将其声明为静态函数或者全局函数。

静态成员函数是不依赖于具体对象的，无需创建任何实例就可以调用，但同时静态成员函数是不可以调用非静态成员的。

另外，有一个corner case,就是如果排序后第一个数是0，则直接返回0，因为后面的数只有可能是0了。

解决了这个问题，我们就很容易写出代码了:

class Solution {
private:
    static bool compTwoString(string& s1,string& s2){
        return s1+s2>s2+s1;
    }
public:
    string largestNumber(vector<int>& nums) {
        if(nums.empty())
            return {};
        vector<string> tmp;
        string res;
        for(int num:nums)
            tmp.push_back(to_string(num));
        sort(tmp.begin(),tmp.end(),compTwoString);
        for(string s:tmp)
            res+=s;
        return res[0]=='0'?"0":res;
    }
};

一道值得反复研究的习题，被归类在Sort中，但除了需要我们利用库函数中的排序，还需要我们另辟蹊径，自定义比较函数，这个拼接字符串的思路值得反复思考。

本作品采用知识共享署名 3.0 中国大陆许可协议进行许可。