剑指offer 33 把数组排成最小的数

转载请注明出处：http://blog.csdn.net/ns_code/article/details/28128551

题目描述：

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

输入：

输入可能包含多个测试样例。 对于每个测试案例，输入的第一行为一个整数m (1<=m <=100)代表输入的正整数的个数。 输入的第二行包括m个正整数，其中每个正整数不超过10000000。

输出：

对应每个测试案例， 输出m个数字能排成的最小数字。

样例输入：

3
23 13 6
2
23456 56

样例输出：

13236
2345656

    这道题主要要自定义一个比较组合后的数字的大小的规则，主要是对于数字m和n，先将其转化为字符串，而后比较其组合mn和nm的大小，这里直接按照字符串的大小标准来比较即可，最后用qsort进行排序，排序后的字符串数组中的字符串从左向右组合起来的字符串即使最小的字符串，即转化为整数后为最小的整数。

    AC代码如下：

[cpp] view plaincopy

1. #include<stdio.h>
2. #include<stdlib.h>
3. #include<string.h>
5. char strs[100][10];  
7. /*
8. 自定义比较规则
9. */
10. int mycompare(const void *str1,const void *str2)  
11. {  
12. static char s1[20];  
13. static char s2[20];  
14. char *string1 = (char *)str1;  
15. char *string2 = (char *)str2;  
16. //将两个字符串合并在一起
17.     sprintf(s1,"%s%s",string1,string2);  
18.     sprintf(s2,"%s%s",string2,string1);  
20. return strcmp(s1,s2);  
21. }  
23. /*
24. 以字符串形式打印出最小的整数
25. */
26. void PrintMinNum(int *nums,int len)  
27. {  
28. if(nums==NULL || len<1)  
29. return;  
31. int i;  
32. //将整数写入到字符串中
33. for(i=0;i<len;i++)  
34.         sprintf(strs[i],"%d",nums[i]);  
36. //按照mycompare中指定的规则排序
37.     qsort(strs,len,10*sizeof(char),mycompare);  
39. for(i=0;i<len;i++)  
40.         printf("%s",strs[i]);  
41.     printf("\n");  
42. }  
45. int main()  
46. {  
47. int nums[100];  
48. int m;  
49. while(scanf("%d",&m) != EOF)  
50.     {  
51. int i;  
52. for(i=0;i<m;i++)   
53.             scanf("%d",nums+i);  
55.         PrintMinNum(nums,m);  
56.     }  
58. return 0;  
59. }  

/**************************************************************

Problem: 1504

User: mmc_maodun

Language: C++

Result: Accepted

Time:240 ms

Memory:1020 kb

****************************************************************/