题解 | #把数组排成最小的数#

32、把数组排成最小的数

解题思路：

要注意题目的意思是把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。

这道题目可以看成是一道排序的题目，因为要使得结果最小，那么给出的整数要怎么排列呢？
其实就可以转化为 A+B 与 B+A 之间比较的问题（注意：这里的A+B并不是A加上B，而是A拼上B），当A+B小于B+A的时候，很明显A要放在B的前面，这样才能使得结果小。

举个例子：

当A = 206，B = 1

此时 A+B = 2061 B+A = 1206

我们可以看到 A+B > B+A，所以很明显B需要放在A的前面，即B+A，才能使得拼出来的数字最小。

我们在来看张动图：

所以总体的逻辑就是：

1、先将整型数组转化为字符串型数组

2、定义特定排序规则

3、用定义的排序规则对字符串型数组进行排序

4、将字符串型数组中每个元素拼接起来

5、得到最小的数

代码：

Java版

public String PrintMinNumber(int [] numbers) {
        if(numbers == null || numbers.length == 0)
            return "";
        int n = numbers.length;
        String[] nums = new String[n];
        // 先将整型数组转化为字符串型数组
        for(int i = 0; i < n; i++){
            nums[i] = numbers[i]+"";
        }
        // 用定义的排序规则对字符串型数组进行排序
        Arrays.sort(nums,(s1,s2)->{
           return (s1+s2).compareTo(s2+s1);
        });

        StringBuffer sb = new StringBuffer();
        // 将字符串型数组中每个元素拼接起来
        for(String num:nums)
            sb.append(num);
        return sb.toString();
    }

复杂度分析：

时间复杂度 O(NlogN) ： N 为 nums数组的长度 ；使用内置函数的平均时间复杂度为 O(NlogN) ，最差为 O(N ² ) 。
空间复杂度 O(N) ： 字符串数组 nums占用线性大小的额外空间。