百度笔试 - 连接数字

题目描述：设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数程序输出：联接成的多位数
例如：n=2时，2个整数32，321连接成的最小整数为：32132，n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
[题目要求]1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。2. 给出算法的时间空间复杂度。3. 证明你的算法。（非常重要）
------------------------------------------------

开始一直在想有没有什么取巧的简单方法，结果搞不定，后来想想还是按排序来吧，容易证明

方法就是把数字做为字符串来排序，排序的比较原则是：两个数字串A，B，如果AB < BA，则A < B

首先证明方法正确性：如果A小于其他所有数字串，则A应该在最前面

假设某个A在中间的连接小于以A开头的连接，则为.....MA....，因为AM < MA，所以AM.... < MA....，

所以把MA换成AM会变小。同理可知把A移到开头最小。

然后具体比较方法：比较字符串的连接

ab|adcde

abcde|ab

拿abcdeab和abcdeab比较

 

代码：

#include
#include
#include
#include

using namespace std;

int main()
{
    string num;
    vector v;
    while(cin>>num) {
        v.push_back(num);
    }
    sort(v.begin(), v.end(), [](const string& s1, const string& s2) -> bool {

        return (s1+s2).compare(s2+s1) < 0;

    });
    for_each(v.begin(), v.end(), [](string s) { cout << s; });
    cout << endl;
   
    return 0;
}