面试题33：把数组排成最小的数

面试题33：把数组排成最小的数

题目

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

暴力解法

排列组合，然后遍历一遍排列组合的结果，得出最小的排列。

算法时间复杂度：

自定义比较规则

比如，如果a和b，排列成ab和ba，如果ab>ba，那么我们就说a>b，反之则是a<b。这就比较简单了：

public String PrintMinNumber(int [] numbers) {
    Integer[] n = new Integer[numbers.length];
    for(int i=0;i<n.length;i++){
        n[i] = numbers[i];
    }
    Arrays.sort(n, new Comparator<Integer>() {
        @Override
        public int compare(Integer o1, Integer o2) {
            int a = o1*power10(Integer.toString(o2).length())+o2;
            int b = o2*power10(Integer.toString(o1).length())+o1;
            return a-b;
        }
    });
    StringBuilder result = new StringBuilder();
    for(int i=0;i<n.length;i++){
        result.append(n[i]);
    }
    return result.toString();
}

private int power10(int n){
    int result = 1;
    for(int i=0;i<n;i++){
        result*=10;
    }
    return result;
}

如果两个正整数拼接起来大于int的表示范围就不行了，所以可以改进一下比较的机制。

public String PrintMinNumber(int [] numbers) {
    String[] n = new String[numbers.length];
    for(int i=0;i<n.length;i++){
        n[i] = Integer.toString(numbers[i]);
    }
    Arrays.sort(n, new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            String a = o1+o2;
            String b = o2+o1;
            for(int i=0;i<a.length();i++){
                if(a.charAt(i)<b.charAt(i)){
                    return -1;
                }else if(a.charAt(i)>b.charAt(i)){
                    return 1;
                }else{
                    continue;
                }
            }
            return 0;
        }
    });
    StringBuilder result = new StringBuilder();
    for(int i=0;i<n.length;i++){
        result.append(n[i]);
    }
    return result.toString();
}

private int power10(int n){
    int result = 1;
    for(int i=0;i<n;i++){
        result*=10;
    }
    return result;
}

算法时间复杂度就是快排的时间复杂度