面试题精选（1）：n个数连接得到最小或最大的多位整数（百度笔试题）
题目描述：
设有n个正整数，将它们联接成一排，组成一个最小的多位整数。
程序输入：n个数
程序输出：联接成的多位数
例如：
n=2时，2个整数32，321连接成的最小整数为：32132，
n=4时，4个整数55，31，312, 33 联接成的最小整数为：312313355
[题目要求]
1. 给出伪代码即可，请给出对应的文字说明，并使用上面给出的例子试验你的算法。
2. 给出算法的时间空间复杂度。
3. 证明你的算法。（非常重要）
分析：（问题归结为排序，但大小比较非一般的比较）
举例说明正常的字符串比较缺陷！如：A=’321’，B=’32’，按照标准的字符串比较规则因为A>B，所以A+B > B+A ，而实际上’32132’ < ’32321’。
所以，自定义一种字符串的比较规则：即如果A+B>B+A,则我们认为A>B。且可以证明：如果A+B>=B+A,B+C>=C+B,则一定有：A+C>=C+A。
这样一来，程序就很简单了。分3步，先把n个数字转换成字符串存储；再按照自定义的规则把n个字符串排序；最后按照从小到大的顺序输出这些字符串（如果从大到小则是求最大的多位整数）。
小结：有些问题看起来是数学问题，认真分析会发现用字符串处理很简单。学会使用string基本函数和集合set的使用……
源代码：
#include <iostream>
#include <set>
#include <string>
using namespace std;
class number
{
public:
number(const char*s):str(s){}
//要使用set集合，对于自定义类型number，要重载'<'运算符
bool operator <(const number &target)const
{
if(str==target.str)
return false; //set中不含重复的元素
string first = str+target.str;
string second = target.str+str;
if(first>second)
return false;
else if(first<second)
return true;
else //这个逻辑不知为什么，应该没有，两个的长度肯定相同
return first.length()<second.length() ? true:false;
};
const char* getStr()const
{
return str.c_str(); //或者return str.data();
};
private:
std::string str;
};
typedef std::set <number> NUMBERS;
void test(number*target,int len)
{
NUMBERS numStrings;
//向set中按从小到大的顺序插入
for(int i=0;i <len;++i)
numStrings.insert(target[i]);
//按顺序输出，就可以实现组成一个最小的多位数，如果反顺序输出则输出一个最大的多位数
for(NUMBERS::iterator IT = numStrings.begin();IT != numStrings.end();++IT)
std::cout<<(*IT).getStr()<<" ";
std::cout<<std::endl;
}
int main()
{
number all3[] = {"432","4321","43214"};
number all[] = {"123","132","213","231","321","312"};
number all1[] = {"123123","12312","1231","123","12","1"};
number all2[] = {"43214321","4321432","432143","43214","4321","432"};
number all4[] = {"12","3"};
//宏DONE是处理函数，sizeof按照类型对齐原则来计算长度
#define DONE(T) test((T),sizeof(T)/sizeof(number))
DONE(all3);
DONE(all);
DONE(all1);
DONE(all2);
DONE(all4);
system("pause");
return 0;
}