剑指 Offer 45. 把数组排成最小的数

解法一 回溯

 直观的解法是求数组内数字的全排列然后比较每个排列的大小取出最小的一种。由于拼接起来的数字可能会非常大，所以会涉及大数问题。可以用字符串解决大数问题，由于每个排列拼接后大小一致所以可以直接使用字符串的比较规则比较字符串大小。
 将字符拼接为字符串比较耗时，所以这种解法会超时。

class Solution {

    private String min;

    public String minNumber(int[] nums) {
        if(nums == null || nums.length == 0)
            return null;
        this.min = arrayToString(nums);
        minNumber(nums, 0);
        return min;
    }

    private void minNumber(int[] nums, int begin) {
        for(int i = begin; i < nums.length; ++i) {
            exch(nums, begin, i);
            String str = arrayToString(nums);
            if(str.compareTo(this.min) < 0){
                this.min = str;
            }
            minNumber(nums, begin + 1);
            exch(nums, begin, i);
        }
    }

    private String arrayToString(int[] nums) {
        StringBuffer buffer = new StringBuffer();
        for(Integer num : nums) {
            buffer.append(num);
        }
        return buffer.toString();
    }

    private void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

解法二 自定义排序规则

&emsp可以有更快的方法，要让数组内拼接成的字符串更小，那么就是要定义一种排序规则，也就是给定两个数字m,n，用一种排序规则判断哪个数字应该排前面。
 由题目可知两个数字可以拼接为 mn 或 nm 如果 mn < nm 那么定义此时m < n; 如果 nm < mn 那么定义此时 n < m; 如果 mn = nm 定义此时 m=n。
两个数字拼接起来会很大，但是拼接后的长度一致所以可以使用字符串的比较规则，从而避免因大数产生的问题。

class Solution {

    private String min;

    public String minNumber(int[] nums) {
        if(nums == null || nums.length == 0)
            return null;
        String[] strNumbers = new String[nums.length];
        for(int i = 0; i < nums.length; i++) {
            strNumbers[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(strNumbers,new Comparator<String>(){
            // 比较哪一个更小，更小的排前面
            public int compare(String o1, String o2) {
                String combine1 = o1 + o2;
                String combine2 = o2 + o1;
                return combine1.compareTo(combine2);
            }
        });
        StringBuffer buffer = new StringBuffer();
        for(String str : strNumbers) {
            buffer.append(str);
        }
        return buffer.toString();
    }
}