首页 > 代码库 > 把数组排成最小的数
把数组排成最小的数
题目:输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出所有数字中的最小一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字321323.
分析:最直接做法是先求出这个数组中所有数字的全排列,然后把每个排列拼起来,求拼起来数字最小的一个。这样做时间复杂度太高。
其实这道题是要我们找到一个排序规则,数组根据这个规则排序之后就能排成一个最小的数字。这个规则应该是两个数字m,n,如果mn<nm则定义m小于n,反之nm<mn则定义n小于m.如果mn=nm则定义n等于m。同时考虑大数问题,有可能拼接起来后超出int型的表示范围。所以将数字转换成字符串。由于mn和nm的位数相同,只需要通过字符串大小比较就可以。
实现如下:其时间复杂度为O(nlogn)。
const int g_MaxNumberLength=10; char* g_StrCombine1=new char[g_MaxNumberLength*2+1]; char* g_StrCombine2=new char[g_MaxNumberLength*2+1]; void PrintMinNumber(int* numbers,int length) { if(numbers==NULL||length<=0) return; char** strNumbers=(char**)(new int[length]); for(int 1=0;i<length;++i) { strNumbers[i]=new char[g_MaxNumberLength+1]; sprintf(strNumbers[i],"%d",numbers[i]); } qsort(strNumbers,length,sizeof(char*),compare); for(int i=0;i<length;++i) printf("%s",strNumbers[i]); printf("\n"); for(int i=0;i<length;++i) delete[] strNumbers[i]; delete[] strNumbers; } int compare(const void* strNumber1,const void* strNumber2) { strcpy(g_StrCombine1,*(const char**)strNumber1); strcat(g_StrCombine1,*(const char**)strNumber2); strcpy(g_StrCombine2,*(const char**)strNumber2); strcat(g_StrCombine2,*(const char**)strNumber1); return strcmp(g_StrCombine1,g_StrCombine2); }
本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1586553
把数组排成最小的数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。