一、题目描述
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
0 < nums.length <= 100
说明:
输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0
二、思路讲解
我们可以看到，最高位最小的数字应该放在前面；最高位相同的，次高位小的数字在前面。所以我们将数字转为字符串，方便比较每一位。
如何定义大小呢？例如3和30相比，显然将30放在3前面，组成的数字要更小，因为330>303。那么就很显而易见了，比较a、b两个数字“大小”的方式就是 a+b<b+a，则说明a应该放在b前面。
于是我们基于快速排序，自定义排序规则。
三、Java代码实现
class Solution { public String minNumber(int[] nums) { int len = nums.length; String []a = new String[len]; for(int i=0; i<len; i++) { a[i] = String.valueOf(nums[i]); } quickSort(a, 0, len-1); StringBuilder res = new StringBuilder(""); for(int i=0; i<len; i++) { res.append(a[i]); } return res.toString(); } /** * 快速排序 */ void quickSort(String []a, int i, int j) { if(i >= j) { return; } int k = partition(a, i, j); quickSort(a, i, k-1); quickSort(a, k+1, j); } /** * 自定义规则的partition排序 */ int partition(String []a, int i, int j) { String position = a[i]; while(i < j) { while(i<j && ((a[j]+position).compareTo((position+a[j]))>=0)) { j--; } a[i] = a[j]; while(i<j && ((a[i]+position).compareTo((position+a[i]))<=0)) { i++; } a[j] = a[i]; } a[i] = position; return i; } }
四、时空复杂度分析
时间复杂度： O(NlogN) 快速排序的时间复杂度
空间复杂度： O(N) StringBuilder的长度
