把数组排成最小的数 AcWing（JAVA）

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

例如输入数组 [3,32,321][3,32,321]，则打印出这 33 个数字能排成的最小数字 321323321323。

数据范围

数组长度 [0,500][0,500]。

样例：

输入：[3, 32, 321] 

输出：321323 

注意：输出数字的格式为字符串。

解题思路： 首先假设数组内的数为 [a, b, c]。若定义一个新的排序方法即 ab > ba,即a在头部的拼接结果比b在头部的拼接结果大，那么就交换a,b在数组内的位置。以这种判断方式排列出来的新数组，从前往后拼接起来就是我们本题需要的最小数。

以下是证明上述排序方式是有意义的：

设a, b, c 的位数分别为n , m , k。

1.若 ab >= ba 且  ab  <=  ba是否能证明 ab = ba。

证明：由于ab与ba位数相同，在数值上比较本假设理应成立，所以此排序满足反对称性。

2.若 ab < ba 且 bc < cb,是否能证明 ac < ca。

证明：ab = a*10^m + b,    ba = b*10^n + a，ac = a*10^k + c, ca = c*10^n +  a;  

  由   ab < ba  得 a/b = (10^n    -   1 )/(10^m      -    1)

由  bc < cb 得b/c = (10^m      -    1)/(10^k      -   1)

只需证明    a/c = (10^n    -     1)/(10^k    -     1)

结论显然成立。即此排序方法满足传递性。

由于sort()方法核心是快速排序，快排核心就是反对称性（特定情况唯一）与 传递性（让数据有梯度）。所以此新定义得排序方法有意义。

最后我们只需证明我们排序后的数组就是最优数组即可：

设我们排序后的数组是 [a, b, c, d]，那么最小数就是 abcd

利用反证法：

假设最小数是acbd,由于a,d所处位置一样所以比较bc,cb大小即可

由我们的新排序定义可知 bc < cb 所以 abcd < acbd,所以假设不成立。

即排序后的数组就是最优数组。

理论成立代码如下：

class Solution {public String printMinNumber(int[] nums) {Integer a[] = new Integer[nums.length];for(int i =0; i < nums.length; i ++) a[i] = nums[i];//只能转换成Integer类Arrays.sort(a, new Comparator<Integer>() {public int compare(Integer o1, Integer o2) {//新排序方法String a = "" + o1;String b = "" + o2;if(Integer.valueOf(a + b) > Integer.valueOf(b + a))return 1;//交换位置else return -1;//不换}});String s1 = "";for(int i = 0; i < a.length; i ++) s1 = s1 + a[i];return s1;} 
}