【牛客刷题专栏】0x32:JZ45 把数组排成最小的数(C语言编程题)

前言

• 个人推荐在牛客网刷题(点击可以跳转)，它登陆后会保存刷题记录进度，重新登录时写过的题目代码不会丢失。
• 个人刷题练习系列专栏：个人CSDN牛客刷题专栏。 题目来自：牛客/题库 / 在线编程 / 剑指offer：
  

---

问题描述：

• 输入一个非负整数数组numbers，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

• 例如输入数组[3，32，321]，则打印出这三个数字能排成的最小数字为321323。

• 1.输出结果可能非常大，所以你需要返回一个字符串而不是整数

• 2.拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

• 数据范围:

• 0<=len(numbers)<=100

---
# 举例：
```c
//示例1：
//输入：
[11,3]
//返回值：
"113"
//=======================
//示例2：
//输入：
[]
//返回值：
""
//=======================
//示例3：
//输入：
[3,32,321]
//返回值：
"321323"
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

---

解法思路：

• 对于两个数 3 和 32 先比较332 >323 所以这里 3>32。也就是在比较两个数字之前 先拼接 然后在比较拼接后的大小

---

代码结果：

 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param numbers int整型一维数组 
 * @param numbersLen int numbers数组长度
 * @return string字符串
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */

//这里写一个两个数字拼接成字符串函数
//num1=12 num2=787 返回12787
int intCat(int num1, int num2) {
    int temp = num2;
    while (temp > 0) {
        temp = temp / 10;
        num1 *= 10;
    }

    return num1 + num2;
}
//写一个整数拼接到字符串后面的函数
void strInt(char* str, int num) {
    int len = 0, temp = num;
    char* str1 = NULL;
    while (temp > 0) {
        temp = temp / 10;
        len++;
    }
    str1 = (char*)malloc(len);
    sprintf(str1, "%d", num);
    strcat(str, str1);
    free(str1);
}
//写一个希尔排序算法
void shell_sort(int* number, int len) {
    for (int gap = len >> 1; gap > 0; gap = gap >> 1) {
        for (int j = gap; j < len; j++) {
            for (int i = j - gap; i >=0; i -= gap) {
                //如果小于 需要交换
                if (intCat(number[i + gap], number[i]) < intCat(number[i], number[i + gap]))
                {
                    int temp = number[i + gap];
                    number[i + gap] = number[i];
                    number[i] = temp;
                }
            }
        }
    }
}
char* PrintMinNumber(int* numbers, int numbersLen) {
    char ans_str[10000] = "";
    shell_sort(numbers, numbersLen);
    for (int i = 0; i < numbersLen; i++)
        strInt(ans_str, numbers[i]);
    return ans_str;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

---

---

结束语

• 以上就是该C语言编程题的内容。可以在牛客尝试刷几道题目来练习实践。牛客网刷题(点击可以跳转)，可以尝试注册使用。
• 题目来自：牛客/题库 / 在线编程 / 剑指offer：