首页 > 代码库 > 把数组排成最小的数

把数组排成最小的数

2024-07-04 08:13:27   224人阅读

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数子中的最小的一个。例如：输入数组{3,32,121}，则打印出 121323 。

我们先把数组中的整数转换成字符串，在函数compare中定义比较规则，并根据该规则用库函数qsort排列。最后把排序好的数组中的数字依次打印出来，就是该数组中数字拼接出来的最小数字。这种思路的时间复杂度是O(nlogn)。

代码如下：

 1 /////////////////////////把数组排成最小的数/////////////////////////////////////////////////
 2 const int g_MaxNumberLength = 10 ;//数的最大位数
 3 char* g_StrCombine1 = new char[g_MaxNumberLength * 2 + 1] ;//创建用于存储合并后的字符串
 4 char* g_StrCombine2 = new char[g_MaxNumberLength * 2 + 1] ;
 5 int compare(const void* str1 , const void* str2)//比较大小的规则
 6 {
 7     strcpy(g_StrCombine1, *(char**)str1);//复制str1 到 g_StrCombine1
 8     strcat(g_StrCombine1, *(char**)str2);//将str2 添加到 g_StrCombine1 末尾
 9 
10     strcpy(g_StrCombine2, *(char**)str2);
11     strcat(g_StrCombine2, *(char**)str1);
12 
13     return strcmp(g_StrCombine1 , g_StrCombine2);//比较合并后的字符串
14 }
15 
16 void PrintMinNumber(int* numbers , int lenght)
17 {
18     char** strNum = new char*[lenght];
19     for (int i = 0 ; i <lenght ; i++)
20     {
21         strNum[i] = new char[g_MaxNumberLength + 1] ;
22         _itoa_s(numbers[i],strNum[i], g_MaxNumberLength+1 ,10);//将整数转换成字符串
23     }
24     qsort(strNum ,lenght ,sizeof(char*), compare);
25 
26     for (int i = 0 ; i < lenght ; i++)
27     {
28         cout<<strNum[i];
29     }
30     for (int i = 0 ; i < lenght ; i++)
31     {
32         delete[] strNum[i] ;//回收分配的内存
33     }
34     delete[] strNum;//回收分配的内存
35 }

 


联系
我们