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

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

分析

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

• 假设数组有n个整数，全排列有n!中可能，求全排列的话，时间复杂度太大。
• 整型最大只能表示到2147483647，也就是全部9位数字和部分10位数字。要是拼接出来的整数大于9位的话就可能产生溢出。所以这还是一道大数问题。

所以我直接跳过这种方法，来看第二种方法：

先将这些整数转化为字符串存储起来，然后对他们排序，排序的规则就是他们拼接起来的字符串的“大小”。比如两个字符串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上：点我前往