首页 > 代码库 > 剑指offer (33) 把数组排成最小的数

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

2024-07-09 13:49:16   215人阅读

题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接处的所有数字中最小的一个

例如输入数组 {3, 32, 321}则打印这3个数字能排成的最小数字 321323

两个数字m和n能拼接成数字mn和nm，如果mn < nm，则打印出mn，也就是m排在n之前，我们定义此时 m 小于 n，也就是相当于 自定义了qsort排序的 函数指针

本题拼接数字可能超出表达范围，需用大数解决

int compare(const void* strNumber1, const void* strNumber2);// int型整数用十进制表示最多只有10位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 i = 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;} // 如果[strNumber1][strNumber2] > [strNumber2][strNumber1], 返回值大于0// 如果[strNumber1][strNumber2] = [strNumber2][strNumber1], 返回值等于0// 如果[strNumber1][strNumber2] < [strNumber2][strNumber1], 返回值小于0int compare(const void* strNumber1, const void* strNumber2){    // [strNumber1][strNumber2]    strcpy(g_StrCombine1, *(const char**)strNumber1);    strcat(g_StrCombine1, *(const char**)strNumber2);     // [strNumber2][strNumber1]    strcpy(g_StrCombine2, *(const char**)strNumber2);    strcat(g_StrCombine2, *(const char**)strNumber1);     return strcmp(g_StrCombine1, g_StrCombine2);}

 


联系
我们