题目描述
输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
最容易想到的就是全排序后进行比较，然而肯定是要进行优化的，优化方式如下：对于数字m和n，可以拼接成mn和nm，如果mn<nm，则说明m应当放在n前面，哪怕还有其他的数也来拼接，都需要保证，所有的拼接方式中，m都在n的前面。
以题目的条件为例，3和321拼接成3321和3213，说明了321一定在3之前，哪怕32最后插在了中间，也要保证这个规则，因此需要重新定义这个规则。而定义完这个规则后就应当进行排序，那么这里就和选择的排序算法有关了。比如思路1是使用了冒泡，而思路2使用的是工具类的排序方式。
思路1：
不调用任何工具类的原始方法。相当于在数组中进行了一次冒泡排序。每次将最大的都放到了数组最后面。根据不同的排序算法，这里有改进的空间。而排序规则就是将相邻的两个字符串合并并比较，将其中可能造成较大值的放在后面。
public class Solution {
public String PrintMinNumber(int [] numbers) {
StringBuilder sb= new StringBuilder();
for (int i=0; i<numbers.length; i++){
for (int j=i+1; j<numbers.length; j++){
int a = Integer.valueOf(numbers[i]+""+numbers[j]);
int b = Integer.valueOf(numbers[j]+""+numbers[i]);
if (a > b){
int t = numbers[i];
numbers[i] = numbers[j];
numbers[j] = t;
}
}
}
for (int i = 0; i < numbers.length; i++) {
sb.append(numbers[i]);
}
return sb.toString();
}
}思路2：
这里使用的是实现Comparator接口的方式
学习了大佬的代码后，改成了自己容易接受的风格，主要学习以下几个点，StringBuilder的使用，实现Comparator接口的匿名内部类的写法。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers==null || numbers.length<=0)
return "";
ArrayList<String> list = new ArrayList<String>();
for(int i = 0; i < numbers.length; i++){
list.add(String.valueOf(numbers[i]));
}
Collections.sort(list,new Comparator<String>(){
@Override
public int compare(String s1,String s2){
String a=s1+s2;
String b=s2+s1;
return a.compareTo(b);
}
});
StringBuilder sb= new StringBuilder();
for(int i = 0; i < numbers.length; i++){
sb.append(list.get(i));//将list集合中的元素添加到字符串中（list中已排序好）
}
return sb.toString();
}
}
//有必要对核心的部分进行解释说明
//在整个Collection.sort方法运行后，完成了所有的比较过程，并且list中都是按照大小顺序摆放的了
//sort(List<T> list, Comparator<? super T> c) 根据某个比较器规则，对list进行排序
Collections.sort源码
public static <T> void sort(List<T> list, Comparator<? super T> c) {
list.sort(c);
}
default void sort(Comparator<? super E> c) {
Object[] a = this.toArray();
Arrays.sort(a, (Comparator) c);
ListIterator<E> i = this.listIterator();
for (Object e : a) {
i.next();
i.set((E) e);
}
}
//比较器只需要告诉我怎么比，然后sort会根据比较值的大小进行排序
//看起来代码中没有写list调整顺序的代码，实际上是由底层的sort完成了顺序的调整。
//这里匿名内部类的写法，变成 Collections.sort(list,new Comparator<String>(){内容});
//因此，重写了compare方法，定义比较规则，并在该规则中，使用的String类的compareTo方法
//compareTo(String anotherString) 按照字典序比较两个字符串。返回值是int 总体上来看，这个方法很高大上，实际上不太容易在第一时间想出来，对我来说，需要的基础和注意的细节较多。比如String类的compareTo方法是按字典序进行排序，直接符合本题要求。否则，需要写一个比较字符串的方法。这题用字典序真的是很巧妙。
写法3：
根据其他人的方法，我自己改成了规则自定义，调用排序方法，哈哈，我真鸡贼。
这个写法，没有引入String类的比较方法，也就是说，不需要知道String类的compare方法的特性，只利用匿名内部类的方式，自定义比较方式。
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
public class Solution {
public String PrintMinNumber(int [] numbers) {
if(numbers==null || numbers.length<=0)
return "";
ArrayList<Integer> list = new ArrayList<>();
for(int i = 0; i < numbers.length; i++){
list.add(numbers[i]);
}
Collections.sort(list,new Comparator<Integer>(){
@Override
public int compare(Integer s1,Integer s2){
int a = Integer.valueOf(s1+""+s2);
int b = Integer.valueOf(s2+""+s1);
return a-b;//这里如果是b-a则是从大到小的排序了
}
});
StringBuilder sb= new StringBuilder();
for(int i = 0; i < numbers.length; i++){
sb.append(list.get(i));//将list集合中的元素添加到字符串中（list中已排序好）
}
return sb.toString();
}
}不是总结的体会：刚开始是随机刷题，难度太大，后来按照offer书上的顺序刷题，发现随着题目的难度的上升，大佬们越来越多的开始使用一些封装好的工具进行解题。原来有些题可能直接调用工具就解出了，现在这些工具只是解题的一部分，不知道最后的笔试和面试对工具类的使用如何定义。大概是题目越复杂，越允许使用工具吧，也可能是根据考察的点，比如如何实现，简单题问你思路，你答个工具实现就不太合适了。
总结：第1种方式是最原始的，排序和定义比较规则都是自己写，第3种写法是稍微讨巧的方式，是排序调用工具类，比较规则自己写。而第2种写法是大佬级别的写法，基础好，排序也调用，规则也直接引用的现成的方法（CompareTo方法）。
京公网安备 11010502036488号