题目描述

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路一

要输出数组的最小排列，那么可以将该数组能够组成的所有排列都列举出来，然后依次比较找出最小排列值；但是n个元素就有n!个全排列数，并且还需要找最小值，这个时间复杂度明显很大。

思路二

该思路不用去找该数组可以组成多少个全排列，而是直接对该数组进行排序，而这里的排序不是简单的根据数组中的元素大小排序，而是我们自定义一个排序规则：根据拼接后的字符串的大小进行排序，如果对于整数m 和整数n,如果mn < nm ,那么我们就设定n应该排序在m的前面

int n;        String s = "";        ArrayList
    
      list = new ArrayList
     
      ();        n = numbers.length;        for(int i = 0; i < n; i ++){
                list.add(numbers[i]);        }        Collections.sort(list, new Comparator
      
       () {
                @Override            public int compare(Integer o1, Integer o2) {
                    String s1 = o1 + "" + o2;//将整数转为字符串                String s2 = o2 + "" + o2;                //小于0：s1
       
         s2  等于0：s1=s2(升序排列)                //将两个int类型的数拼接为字符串的形式进行比较可以防止溢出（隐形的大数问题）                return s1.compareTo(s2);//虽然比较的拼接的字符串大小，但是最后还是根据字符串的大小来对数组的元素进行排序，只不过我们只是参照字符串的比较这个标准来进行排序的，而不是简单的升序或者降序排列            }        });		//拼接字符串        for(int j:list){
    								//foreach语句            s += j;        }        return s;
       
      
     
    

• 注意如果这里return s2.compareTo(s1)，那么最终就是按照最大排列进行比较了，最后返回的就是降序排列的数组

• 这里借助了

  public static 
        
          void sort(List
         
           list, Comparator
           c) {
            list.sort(c);}
         
        

自己构建一个Comparator，自定义排序方法

《算法导论》第三版