输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组 {3,32,321},则打印出这三个数字能排成的最小数字为 321323。
可以看成是一个排序问题,在比较两个字符串 S1 和 S2 的大小时,应该比较的是 S1+S2 和 S2+S1 的大小,如果 S1+S2 < S2+S1,那么应该把 S1 排在前面,否则应该把 S2 排在前面。
import java.util.*;
import java.lang.*;
public class Solution {
public String PrintMinNumber(int [] numbers) {
// 通过比较字符串思想拼接最小值
String[] arr = new String[numbers.length];
for(int i = 0; i < numbers.length; i++) {
arr[i] = String.valueOf(numbers[i]);
}
// 快排比较 手写快排会更快点
// Arrays.sort(arr,(x,y) -> (x + y).compareTo(y + x)); // 函数编程
sorted(arr, 0, numbers.length - 1);
// 输出拼接
StringBuilder res = new StringBuilder();
for(String s : arr) {
res.append(s);
}
return res.toString();
}
void sorted(String[] arr, int l, int r) {
if(l >= r)
return;
int i = l, j = r;
String temp = arr[l];
while(i < j) {
while((arr[j]+arr[l]).compareTo(arr[l]+arr[j]) >= 0 && i < j) j--; // 此处注意ij顺序对应关系防止死循环
while((arr[i]+arr[l]).compareTo(arr[l]+arr[i]) <= 0 && i < j) i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[i] = arr[l];
arr[l] = temp;
sorted(arr, l, i-1);
sorted(arr, i+1, r);
}
}