题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
分析
最直接的方法是，将这几个数做全排列，得到所有可能的组合，然后对组合排序，选出最小的数。第二种方法是，设计一种排序方法，字符串m和n拼接，如果mn >nm,那么字符串n应该排在m的前面。
代码一
public String PrintMinNumber(int [] numbers) {
if(numbers == null || numbers.length == 0) return "";
String[] nums = new String[numbers.length];
StringBuilder sb = new StringBuilder();
for(int i=0;i<numbers.length;i++)
nums[i] = ""+numbers[i];
Arrays.sort(nums,new Comparator<String> () {
public int compare(String o1,String o2) {
return (o1+o2).compareTo(o2+o1);
}
});
for(int i=0;i<numbers.length;i++)
sb.append(nums[i]);
return sb.toString();
}
代码二：全排列
ArrayList<String> res = new ArrayList<>();
public String PrintMinNumber(int [] numbers) {
permutation(numbers,0);
String[] nums = new String[res.size()];
for(int i=0;i<res.size();i++)
nums[i] = res.get(i);
Arrays.sort(nums);
return nums[0];
}
private void permutation(int[] numbers,int pos) {
if(pos >= numbers.length) {
StringBuilder sb = new StringBuilder();
for(int i=0;i<numbers.length;i++)
sb.append(""+numbers[i]);
res.add(sb.toString());
return;
}
for(int i=pos;i<numbers.length;i++) {
swap(numbers,pos,i);
permutation(numbers,pos+1);
swap(numbers,pos,i);
}
}
private void swap(int[] numbers, int i,int j) {
int tmp = numbers[i];
numbers[i] = numbers[j];
numbers[j] = tmp;
}
