剑指Offer：[第16天 排序(简单)]---＞把数组排成最小的数

一、题目描述二、思路分析三、整体代码

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

示例1：

输入: [10,2]
输出: "102"

示例2：

输入: [3,30,34,5,9]
输出: "3033459"

提示：

0 < nums.length <= 100

说明：

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

注：思路分析中的一些内容和图片参考自力扣各位前辈的题解，感谢他们的无私奉献

思路

此题求拼接起来的最小数字，本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y，则规定排序判断规则 为：
若拼接字符串 x + y > y + x x + y > y + x x+y>y+x，则 x x x 大于 y y y
反之，若 x + y < y + x x + y < y + x x+y x x x 小于 y y y 代表：排序完成后，数组中 x x x 应在 y y y 左边，大于则反之。

证明： 字符串 x y < y x , y z < z y xy < yx , yz < zy xy 设十进制数 x x x, y y y, z z z 分别有 a a a, b b b, c c c 位，则有：
(左边是字符串拼接，右边是十进制数计算，两者等价)
x y = x ∗ 1 0 b + y xy = x * 10^b + y xy=x∗10b+y
y x = y ∗ 1 0 a + x yx = y * 10^a + x yx=y∗10a+x
则 x y < y x xy < yx xy x ∗ 1 0 b + y < y ∗ 1 0 a + x x * 10^b + y < y * 10^a + x x∗10b+y x ( 1 0 b − 1 ) < y ( 1 0 a − 1 ) x (10^b - 1) < y (10^a - 1) x(10b−1) x / ( 1 0 a − 1 ) < y / ( 1 0 b − 1 ) x / (10^a - 1) < y / (10^b - 1) x/(10a−1) 同理， 可将 y z < z y yz < zy yz y / ( 1 0 b − 1 ) < z / ( 1 0 c − 1 ) y / (10^b - 1) < z / (10^c - 1) y/(10b−1) 将 ① ② 合并，整理得：
x / ( 1 0 a − 1 ) < y / ( 1 0 b − 1 ) < z / ( 1 0 c − 1 ) x / (10^a - 1) < y / (10^b - 1) < z / (10^c - 1) x/(10a−1) x / ( 1 0 a − 1 ) < z / ( 1 0 c − 1 ) x / (10^a - 1) < z / (10^c - 1) x/(10a−1) x ( 1 0 c − 1 ) < z ( 1 0 a − 1 ) x (10^c - 1) < z (10^a - 1) x(10c−1) x ∗ 1 0 c + z < z ∗ 1 0 a + x x * 10^c + z < z * 10^a + x x∗10c+z ∴ 可推出 x z < z x xz < zx xz 算法流程：
①初始化：字符串列表strs，保存各数字的字符串格式
②列表排序：应用以上排序判断规则，对strs执行排序
③返回值：拼接strs中的所有字符串，并返回
复杂度分析：
复杂度分析：
时间复杂度 O ( N l o g N ) rm{O(NlogN)} O(NlogN)：N为最终返回值的字符数量(strs列表的长度 ≤ N rm{leq N} ≤N)。使用快排或内置函数的平均时间复杂度为 O ( N l o g N ) rm{O(NlogN)} O(NlogN) ，最差为 O ( N 2 ) rm{O(N^2)} O(N2)
空间复杂度 O ( N ) rm{O(N)} O(N)：字符串列表strs占用线性大小的额外空间
案例分析：

整体代码如下

//自定义的比较方法
int compare(const void *a, const void *b)
{
    char num1[24];
    char num2[24];
	//把传进来的两个数转换成字符串
    sprintf(num1, "%d%d", *(int *)a, *(int *)b);
    sprintf(num2, "%d%d", *(int *)b, *(int *)a);
    //将其按照 "从小到大的顺序排列"
    return strcmp(num1, num2);
}

char* minNumber(int* nums, int numsSize){
    char *res = (char *)malloc(sizeof(char) * 1200); //用于返回字符串
    char *p = res;   //让p指向返回的字符串，并用p控制进行后续操作
    qsort(nums, numsSize, sizeof(int), compare); //对nums数组进行排序
    //将nums的每个元素转换成字符，并加在P后面
    for (int i = 0; i < numsSize; i++)  
        p += sprintf(p, "%d", nums[i]);
    *p = '';  //加上字符串结尾符
    return res; //返回字符串的首地址
}

运行，测试通过