题目描述

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

思路

1. 暴力法：找出数组中所有的组合情况，一一对比找最小
2. 排序：按照特定的方法排序（使两个字符串组合起来最小，小的那个排前面）

实现

1. 暴力法

   public String PrintMinNumber(int [] numbers) {
        if(numbers.length==0){
            return "";
        }
        ArrayList<String> r = f(numbers, 0, numbers.length-1);
        String min = r.get(0);
        for(String s:r){
            if(s.compareTo(min)<0){
                min=s;
            }
        }
        return min;
    }

    //此函数返回所有的遍历情况
    public ArrayList<String> f(int[] numbers, int start, int end){
        if(start>=end){
            ArrayList r= new ArrayList<String>();
            r.add(String.valueOf(numbers[start]));
            return r;
        }
        ArrayList r= new ArrayList<String>();
        //替换头，以遍历所有的情况
        for(int i=start;i<=end;i++){
            //swap
            int temp=numbers[start];
            numbers[start]=numbers[i];
            numbers[i]=temp;
   
            for(String s:f(numbers, start+1, end)){
                r.add(String.valueOf(numbers[start])+s);
            }
            //交换了的数要再换回来，以便下次继续交换
            temp=numbers[start];
            numbers[start]=numbers[i];
            numbers[i]=temp;
        }
        return r;
    }

2. 排序：

   //采用冒泡排序，也可以使用快排等其他排序算法
   public String PrintMinNumber(int [] numbers) {
        if(numbers.length==0){
            return "";
        }
   
        for(int k=0;k<numbers.length;k++){
            for(int i=k;i<numbers.length-1;i++){
                if(Compare(numbers[i], numbers[i+1)>0){
                    //swap
                    int temp=number[i];
                    number[i]=number[i+1];
                    number[i+1]=temp;
                }
            }
        }
   
        //sort complate
        StringBuilder result=new StringBuilder();
        for(int i:numbers){
            result.add(String.valueOf(i));
        }
        return result.toString();
   
    }

   //具体的两数比较方法
   public int Compare(int m, int n){
    m_str=String.valueOf(m);
    n_str=String.valueOf(n);
    c1=m_str+n_str;
    c2=n_str+m_str;
    if(c1.compareTo(c2)<0){
        return -1;
    }else if(c1.compareTo(c2)==0){
        return 0;
    }else{
        return 1;
    }
   }