Question

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

这个题目最直接的做法应该是先求出这个数组中所有数字的全排列，然后把每个排列拼起来，最后求出拼起来的数字的最大值。求数组的排列和面试题28字符串的排列非常类似，这里不再详细介绍。根据排列组合的知识，n个数字总共有n!个排列。我们再来看一种更快的算法。

这道题其实是希望我们能找到一个排序规则，数组根据这个规则排序之后能排成一个最小的数字。要确定排序规则，就要比较两个数字，也就是给出两个数字m和n，我们需要确定一个规则判断m和n哪个应该排在前面，而不是仅仅比较这两个数字的值哪个更大。

根据题目的要求，两个数字m和n能拼接成数字mn和nm。如果mn<nm，那么我们应该打印出mn，也就是m应该排在n的前面，我们定义此时m小于n；反之，如果nm<mn，我们定义n小于m。如果mn=nm，m等于n。在下文中，符号<、>及=表示常规意义的数值的大小关系，而文字大于、小于、等于表示我们新定义的大小关系。

接下来考虑怎么去拼接数字，即给出数字m和n，怎么得到数字mn和nm并比较它们的大小。直接用数值去计算不难办到，但需要考虑到一个潜在的问题就是m和n都在int能表达的范围内，但把它们拼起来的数字mn和nm用int表示就有可能溢出了，所以这还是一个隐形的大数问题。

一个非常直观的解决大数问题的方法就是把数字转换成字符串。另外，由于把数字m和n拼接起来得到mn和nm，它们的位数肯定是相同的，因此比较它们的大小只需要按照字符串大小的比较规则就可以了。

基于这个思路，我们可以写出如下代码：

在上述代码中，我们先把数组中的整数转换成字符串，在函数compare中定义比较规则，并根据该规则用库函数qsort排序。最后把排好序的数组中的数字依次打印出来，就是该数组中数字能拼接出来的最小数字。这种思路的时间复杂度和qsort的时间复杂度相同，也就是O（nlogn），这比用n!的时间求出所有排列的思路要好很多。

上述思路中，我们定义了一种新的比较两个数的规则，这种规则是不是有效的？另外，我们只是定义了比较两个数的规则，却用它来排序一个含有多个数字的数组，最终拼接数组中的所有数字得到的是不是真的就是最小的数字？一些严格的面试官还会要求我们给出严格的数学证明，以确保我们的解决方案是正确的。

我们首先证明之前定义的比较两个数字大小的规则是有效的。一个有效的比较规则需要3个条件：自反性、对称性和传递性。我们分别予以证明。

（1）自反性：显然有aa=aa，所以a等于a。

（2）对称性：如果a小于b，则ab<ba，所以ba>ab，因此b大于a。

（3）传递性：如果a小于b，则ab<ba。假设a和b用十进制表示时分别有l位和m位，于是ab=a×10^m＋b，ba=b×10^l＋a。

ab<ba→a×10^m＋b<b×10^l＋a→a×10^m－a< b×10^l－b

→a（10^m－1）<b（10^l－1）→a/（10^l－1）<b/（10^m－1）

同时如果b小于c，则bc<cb。假设c用十进制表示是有n位，和前面的证明过程一样，可以得到b/（10^m－1）<c/（10ⁿ－1）。

a/（10^l－1）<b/（10^m－1）并且b/（10^m－1）<c/（10ⁿ－1）→a/（10^l－1）<c/（10ⁿ－1）→a（10ⁿ－1）<c（10^l－1）

→a×10ⁿ＋c<c×10^l＋a→ac<ca→a小于c

于是我们证明了这种比较规则满足自反性、对称性和传递性，是一种有效的比较规则。接下来我们证明根据这种比较规则把数组排序之后，把数组中的所有数字拼接起来得到的数字的确是最小的。直接证明不是很容易，我们不妨用反证法来证明。

我们把n个数按照前面的排序规则排序之后，表示为A₁A₂A₃…A_n。假设这样拼接出来的数字并不是最小的，即至少存在两个x和y（0<x<y<n），交换第x个数和第y个数后，A₁A₂…A_y…A_x…A_n<A₁A₂…A_x…A_y…A_n。

由于A₁A₂…A_x…A_y…A_n是按照前面的规则排好的序列，所以有A_x小于A_x＋1小于A_x＋2小于…小于A_y－2小于A_y－1小于A_y。

由于A_y－1小于A_y，所以A_y－1A_y<A_yA_y－1。我们在序列A₁A₂…A_x…A_y－1A_y…A_n中交换A_y－1和A_y，有A₁A₂…A_x…A_y－1A_y…A_n<A₁A₂…A_x…A_yA_y－1…A_n（这个实际上也需要证明，感兴趣的读者可以自己试着证明）。我们就这样一直把A_y和前面的数字交换，直到和A_x交换为止。于是就有A₁A₂…A_x…A_y－1A_y…A_n<A₁A₂…A_x…A_yA_y－1…A_n<A₁A₂…Ax…A_yA_y－2A_y－1…A_n<…<A₁A₂…A_yA_x…A_y－2A_y－1…A_n。

同理由于A_x小于A_x＋1，所以A_xA_x＋1<A_x＋1A_x。我们在序列A₁A₂…A_yA_xA_x＋1…A_y－2A_y－1…A_n中只交换A_x和A_x＋1，有A₁A₂…A_yA_xA_x＋1…A_y－2A_y－1…A_n<A₁A₂…A_yA_x＋1A_x…A_y－2A_y－1…A_n。我们接下来一直拿A_x和它后面的数字交换，直到和A_y－1交换为止。于是就有A₁A₂…A_yA_xA_x＋1…A_y－2A_y－1…A_n<A₁A₂…A_yA_x＋1A_x…A_y－2A_y－1…A_n<…<A₁A₂…A_yA_x＋1A_x＋2…A_y－2A_y－1A_x…A_n。

所以A₁A₂…A_x…A_y…A_n<A₁A₂…A_y…A_x…A_n，这和我们的假设的A₁A₂…A_y…A_x…A_n<A₁A₂…A_x…A_y…A_n相矛盾。

所以假设不成立，我们的算法是正确的。

源代码：

本题完整的源代码详见33_SortArrayForMinNumber项目。

测试用例：

- 功能测试（输入的数组中有多个数字，输入的数组中的数字有重复的数位，输入的数字只有一个数字）。

- 特殊输入测试（表示数组的指针为NULL指针）。

本题考点：

- 本题有两个难点；第一个难点是想出一种新的比较规则来排序一个数组；第二个难点在于证明这个比较规则是有效的，并且证明根据这个规则排序之后把数组中所有数字拼接起来得到的数字是最小的。要想解决这两个难点，都要求应聘者有很强的数学功底和逻辑思维能力。

- 考查解决大数问题的能力。应聘者在面试的时候要意识到，把两个int型的整数拼接起来得到的数字可能会超出int型数字能够表达的范围，从而导致数字溢出。我们可以用字符串表示数字，这样就能简洁地解决大数问题。