面试题33:把数组排成最小的数

题目:输入一个正整数数组,把数组中所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这3个数字能排列成的最小数字321323。


分析

很容易想到的是求出所有整数的全排列,然后将它们拼接为一个数字,找出最小的一组。但这种方法存在两个问题:

所以我直接跳过这种方法,来看第二种方法:

先将这些整数转化为字符串存储起来,然后对他们排序,排序的规则就是他们拼接起来的字符串的“大小”。比如两个字符串m和n,可以拼接成mn和nm,由于他们的长度相同,所以可以用strcmp(mn,nm)来比较。如果strcmp函数返回1,表明字符串mn“大于”nm;否则nm“大于”mn。然后将他们顺次拼接起来即可。因为在排序函数中会将字符串两两比较,所以可以确保他们拼接出来的是有序的。

代码如下:

bool compair(const string& s1,const string& s2)
{
    string news1=s1+s2;
    string news2=s2+s1;
    int ret=strcmp(news1.c_str(),news2.c_str());
    if(ret<=0)
        return true;
    else
        return false;
}

void PrintMinNumber(vector<int> v)
{
    if(v.size()==0)
        return;
    vector<string> vs;
    char tmp[11];
    int i;
    for(i=0;i<v.size();++i)
    {
        sprintf(tmp,"%d",v[i]);
        vs.push_back(string(tmp));
    }
    sort(vs.begin(),vs.end(),compair);
    for(i=0;i<vs.size();++i)
    {
        cout<<vs[i];
    }
    cout<<endl;
    return;
}

以上

如果你有任何想法或是可以改进的地方,欢迎和我交流!

完整代码及测试用例在github上:点我前往

[来自为知笔记(Wiz)](http://www.wiz.cn/i/96171253 "来自为知笔记(Wiz)")