题目描述
- 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
解题思路
- 将数组数字重排为最小的数字连接形式，那么直接遍历数组就可以得到我们想要的结果
- 那么问题来了怎么重组这个排序呢，按照一般的数字排序，就是两个数比较大小然后交换位置，那么这个组合成字符串的我们可以采用两个数字a和b组合成字符串ab和字符串ba比较这两个字符串的大小来确定他们的位置，如果说ab结果比较小，那就代表不需要交换，如果ba小那就代表需要将数字b挪到a之前进行一次交换
- 确定了比较方法现在需要确定排序方法，排序有N种方法，归并/堆排/快排/选择/插入/希尔/冒泡等一堆方法，当然快的也就是快排了，时间复杂度O(nlogn)那就这个了
- 方法和数字的数组快排完全一样，只是将交换的判断条件更改为2中所述的内容即可
- 最后遍历数组重组为字符串
Java源代码
import java.util.ArrayList;
public class Solution {
public String PrintMinNumber(int [] numbers) {
sort(numbers, 0, numbers.length-1);
String result = "";
for (int i=0; i<numbers.length; i++) result += String.valueOf(numbers[i]);
return result;
}
private static void sort(int[] nums, int lo, int hi) {
if (hi<=lo) return;
int j = partion(nums, lo, hi);
sort(nums, lo, j-1);
sort(nums, j+1, hi);
}
private static int partion(int[] nums, int low, int high) {
int key = nums[low];
while (low<high) {
while (low<high && compare(key, nums[high])) high--;
if (low<high) nums[low] = nums[high];
while (low<high && compare(nums[low], key)) low++;
if (low<high) nums[high] = nums[low];
}
nums[low] = key;
return low;
}
private static boolean compare(int a, int b) {
String ab = String.valueOf(a) + String.valueOf(b);
String ba = String.valueOf(b) + String.valueOf(a);
return ab.compareTo(ba)<=0;
}
}
