一道朴实无华的算法题：把数组排成最小的数

今天分享的题目来源于 LeetCode 上的剑指 Offer 系列 面试题45 把数组排成最小的数。

这道题目有好几个读者反馈说在字节二面环节中遇到过，所以今天提前来讲，希望对你有所帮助。

题目链接：https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof/

题目描述

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

示例1

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

示例2

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

题目解析

暴力破解

给定一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。所有数字中最小的一个，对一个包含 n 个非负整数的数组，所有的组合数为 个，然后对这 的组合进行排序找出最小的一个。

比如对数组 [10，2] 而言，其所有的组合就是 [ "102"、"210"]  ，然后比较 102 和 210 ，显然是 102 比较小，输出即可。

但是问题是，当这个数组特别大的时候，组合而成的数字就会特别大，用任何一个整数类型（int ，long）都无法表示，这里隐含一个大数问题，所以还是要考虑用字符串来进行大小比较。

还是以数组 [10，2]  为例，可以组合成字符串 "102" 和 "210" ，比较这两个字符串，“102” < “210” ，所以输出 "102" ，当然这里只是初探。

转化思想

伪贪心方法

为何叫伪贪心呢？

我们以数组 [3,30,34,5,9] 为例进行说明

对于 3 和 30 而言，可以组合出的字符串为 "303" 和 "330"  ，”303“ < “330”，所以保留 ”303“。

将 “303” 和 34 继续进行拼接，可以拼接为 "30334"  和  "34303"  ，”30334″ < “34303”，所以保留 ”30334“；

将 “30334” 和 5 继续进行拼接，可以拼接为 "303345"  和  "530334"  ，”303345″ < “530334”，所以保留 ”303345“；

将 “303345” 和 9 继续进行拼接，可以拼接为 "9303345"  和  "3033459"  ，”3033459″ < “9303345”，所以保留 ”3033459“；

即拼接出的最小的数字为 “3033459”；

因为在每一次与后续的数字组合的时候，我们都是 尽可能选择当前组合最小 的数字组合，然后一直向下，直到将所有的数字都拼接到字符串当中。

但是我们开心的太早了，因为这个例子实在太特殊了，为什么说他特殊呢？

因为数组  [3,30,34,5,9]  按照字符串的大小比较规则，"3" < "30" < "34" < "5" < "9" ，也就说这个数组按照字符串的大小比较规则，是一个有序的数组且是一个升序的字符串数组，所以我们才能按照前面的 “所谓的贪心” 方法得到拼接后最小的数字组合 "3033459" ，但事实上是：

给定一个非负整数数组，只要把非负整数数组当中的数字按照比较规则进行升序排列之后，然后将排序后的字符串数组连接起来就是能拼接出的所有数字组合中最小的一个。

而这个比较规则就是对于任意个两个数字字符串 m 和 n ，如果 m + n < n + m ，则应该将 m 排在 n 的前面。

为什么这个方法就是合理的呢？

我们以数组  [3,30,34]  进行说明（因为数组太大组合太多，并不能大家很好的理解），写出数组中数字可以拼接成的所有组合：

我们可以看到，数组总共可以得到  中组合，但其中只有一个组合是最小的，就是图中左箭头所指的字符串 “30334”，我们对数组  [3,30,34]  按照比较规则进行排序：

m = “30”，n = “3”，∵ “303” < “330”，∴ ”30“ 应该排在 ”3“ 的前面；

同理，∵ “334” < “343”，∴ ”3“ 应该排在 ”34“ 的前面；

那么 “30” 排在 “34” 的前面是否合理呢？

∵ “3034” < “3430”，∴ ”30“ 排在 ”34“ 的前面是合理，这也就是排序规则传递性的一个体现；

所以最终的得到的排序字符串数组为  ["30","3","34"]  ，这也是我们最终需要输出的最小组合的顺序。

我们为什么将本为数字的数组转化为字符串数组之后，按照既定的规则排序，就是最小组合的顺序呢？

这里谈的就是个人的一些理解，可能有误，还望批评指正。

原因有三：

1. 对数字组合之后得到的数组太大，无法用任何一个整数类型表示，所以考虑使用字符串进行处理（隐含的大数问题）；
2. 将数字转化为字符串之后，可以组合出的字符串个数没变，但是将组合后的字符串的进行纵向比较，你会发现，一定是尽可能将最小的数字向前排，才能得到最小的组合。
3. 将最小的数字向前排，这里的排序规则就是对于任意个两个数字字符串 m 和 n ，如果 m + n < n + m（+ 表示连接） ，则应该将 m 排在 n 的前面。

排序规则正确性证明

对于任意的两个数字字符串 m 和 n：

1. 若 m + n = n + m ，则 m = n;
2. 若 m + n < n + m，则 m < n;
3. 若 m + n > n + m ，则 m > n;

一个有效的比较规则满足三个条件：自反性、对称性和传递性（离散数学）。

（1）自反性

对于任意一个字符串 m ，显然  m + m = m + m，所以 m = m；

（2）对称性

对于任意字符串 m 和 n，如果 m + n < n + m，则 m < n，∴ n + m > m + n，∴ n > m；

（3）传递性（之前在例子当中有说明）

对于任意的数字字符串 m 、k 和 n，若 m + k < k + m 且  k + n < n + k ，则 m < n;

对于任意的数字字符串 m 、k 和 n，若 m + k < k + m，则 m < k；∵ k + n < n + k，∴ k < n；∴ m < n;

传递性更严格的证明：

对于任意的数字字符串 m 和 k ，若 m < k，则 m + k < k + m（+ 表示连接）。设 m 和 k 分别为 i 位 和 j 位，则 m 和 k 连接的结果就等于 （这里是加号），k 和 m 连接的结果就等于  。这里其实不难理解，比如数字 3 和 30 连接就是 ，而 30 和 3 连接就是 .

则 m + k < k + m 可以表示为

左右两侧移项：

提取公因子并移项（注意这里的 i 和 j 都是 大于等于 1的，所以可以直接移项）：

→

设 n 为 h 位，且 k < n，则 k + n < n + k。同理可以得到：

→

所以

继而得到

继而得到   ，所以 m < n。

由于排序规则满足自反性、对称性和传递性，所以排序规则有效。

将你的思想转变过来

此时问题就不再是我们读到的那样 “给定一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个”，而是 ”给定一个非负整数数组，然后对非负整数数组按照上面所证明的排序规则进行排序即可“。

算法流程也就清晰可见：

1. 初始化：将给定的数组 nums 的所有数字转化为字符串，并存入字符串数组 nums_str 中；
2. 按照上面证明的排序规则，对 nums_str 进行排序；
3. 对排序后的 nums_str 进行拼接即可。

实现代码

此时实现代码就转化为你对排序算法的掌握程度了，使用不同的排序算法，也会得到不同的实现方式，这里我们以快速排序为例。

class Solution {
    public String minNumber(int[] nums) {
        String nums_str[] = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            nums_str[i] = String.valueOf(nums[i]);
        }
        QuickSort(nums_str, 0, nums.length-1);
        String result = new String();
        for(String s : nums_str){
            result += s;
        }
        return result;
    }
    public static void QuickSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        QuickSort(strs, l, i - 1);
        QuickSort(strs, i + 1, r);
    }
}

还有一种使用内置函数的实现方式，只需要为内置函数指定排序规则即可。

Arrays.sort(nums_str, (m,n) -> (m + n).compareTo(n + m))

其中 (m,n) -> (m + n).compareTo(n + m) 就是自定义的 Comparator （比较器，也就是排序规则，对于任意两个数字字符串，如果 （m + n） < (n + m)，则应该将 m 排在 n 的前面）。

与前一种采用快速排序的方式，这里也就更改了排序方式的一行代码。

class Solution {
    public String minNumber(int[] nums) {
        String nums_str[] = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            nums_str[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(nums_str, (m,n) -> (m + n).compareTo(n + m));
        String result = new String();
        for(String s : nums_str){
            result += s;
        }
        return result;
    }
}

复杂度分析

• 时间复杂度：这里的时间复杂度取决于你使用的排序算法，比如你采用冒泡排序，时间复杂度就是 ；而采用快速排序，时间复杂度就是 。至于 Java 内置的排序算法，具体采用哪种需要依据与排序的数组大小，所以无法给出一个肯定的时间复杂度。
• 空间复杂度：空间复杂度很明显，就是我们将 nums 当中的所有数字转化为字符串之后存储所需的空间 nums_str ，空间复杂度为 .

知识点

排序算法、排序规则有效性的证明、思维方式的转变。