題目描述
輸入一個正整數(shù)數(shù)組萄唇,把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)巩检,打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組{3焕刮,32舶沿,321}墙杯,則打印出這三個數(shù)字能排成的最小數(shù)字為321323配并。
分析
最直接的方法是,將這幾個數(shù)做全排列高镐,得到所有可能的組合溉旋,然后對組合排序,選出最小的數(shù)嫉髓。第二種方法是观腊,設(shè)計一種排序方法,字符串m和n拼接算行,如果mn >nm,那么字符串n應(yīng)該排在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;
}