面试题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。然后将他们顺次拼接起来即可。因为在排序函数中会将字符串两两比较,所以可以确保他们拼接出来的是有序的。

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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上:点我前往

<div>来自为知笔记(Wiz)</div>