leetcode的最大数字：有人能解释一下为什么这个方法有效吗？

Question

class Solution {
public:
    string largestNumber(vector<int> &num) {
        vector<string> arr;
        for(auto i:num)
            arr.push_back(to_string(i));
        sort(begin(arr), end(arr), [](string &s1, string &s2){ return s1+s2>s2+s1; });
        string res;
        for(auto s:arr)
            res+=s;
        while(res[0]=='0' && res.length()>1)
            res.erase(0,1);
        return  res;
    }
};

我很困惑为什么这个方法有效…有人能给这个方法一个证明吗？

Answer 1

首先要注意的是，你用向量的所有元素形成的每一个数都有相同的位数。这就是为什么我们可以对字符串使用词典排序。

所以我们可以用一种简单的方法来列出所有的posibile连接，然后从中选择最大的连接。

用于排序的字符串比较对于向量中的2个元素的特殊情况利用了上面提到的事实。因此，我们可以修改简单的实现，首先使用这个比较器搜索最大的to元素，将它们串联起来，然后用一个大小减小了1的向量重复（新串联的元素也包含在新向量中）。但话又说回来，我们会选择新连接的元素和剩余的最大元素继续。如果我们不选择新连接的元素，那么我们就不会选择向量中最大的两个元素。所以我们按照递减的顺序，把元素一个一个地挑出来。这就是排序首先应用的原因。