【剑指Offer】面试题45：把数组排成最小的数

发表于 | 分类于 | 阅读次数:

题目：输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如，输入数组 {3, 32, 321}，则打印出这 3 个数字能排出的最小数字 321323。

思路 1：全排列

最直接的思路是：求出数组中所有数字的全排列，然后找出最小的数字。这样的做法着实简单，但是时间复杂度为 O(n!)，较高，我们需要找到更快的算法。

思路 2：大小比较

我们可以尝试举例来寻找思路，{3, 32, 321} 可以排列出 332321, 332132, 323321, 323213, 321332 和 321323。将结果从小到大排序是 321323, 321332, 323213, 323321, 332132, 332321。这里我们可以发现把 321 排在前面会使得结果变小，把 3 排在前面会使得结果变大。

我们可以定义一组比较规则，来比较数组中数字的“大小”。规则如下：对于 m 和 n，如果 mn < nm，那么 m < n；如果 mn = nm，那么 m = n；如果 mn > nm，那么 m > n。使用这组规则可以将数组中的数字进行从小到大排序，然后按照顺序拼接成一个数字，这个数字就是我们要找的结果。

这里存在一个隐晦的问题，在比较的时候，两个 int 数字拼接起来是一个大数问题。因此，我们可以使用字符串将这两个数字拼接，由于 mn 和 nm 的位数相同，我们便可以直接使用字符串比较大小。

我们总结一下这个思路：首先定义一组规则，来比较数组中数字的“大小”，然后使用这组规则可以将数组中的数字进行从小到大排序，然后按照顺序拼接成数字。

由于排序操作需要 $O(n\,log\,n)$ 的时间复杂度，其他的操作均小于它，因此这个算法的时间复杂度是 $O(n\,log\,n)$。

这个算法涉及到自己定义的比较规则，往往需要证明这个规则的有效性与这个算法的有效性。换句话说，也就是需要证明规则是自反的、对称的和传递的；该算法确实能够找到最小的数字。这个部分比较长，就省略拉。

实现

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
import java.util.*;

public class Solution {
    public String PrintMinNumber(int[] numbers) {
        // 特殊输入的检查
        if (numbers == null || numbers.length == 0)
            return "";

        // 构建列表
        List<Integer> l = new ArrayList<>();
        for (int n: numbers)
            l.add(n);

        // 自定义排序
        l.sort(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return ("" + o1 + o2).compareTo("" + o2 + o1);
            }
        });

        // 按排序结果输出
        StringBuilder res = new StringBuilder();
        for (int n: l)
            res.append(n);

        return res.toString();
    }
}