把数组排成最小的数（剑指offer 面试题33）

题目：输入数组{3,32,321}，得到321323

思路：
首先想到的是全部的排列有n!个，可以在排列的时候进行剪枝。
但这更像一个排序问题，对于数组中的两个数m和n，排列可以得到mn和nm，如果mn小，那么m需要排在n前面，反之依然（这个是需要证明的）。同时还需要考虑大数的问题，我们刚好可以利用字符串来解决大数问题，mn和nm的比较也刚好可以用字符串的比较来解决。

ConcatenateNumber 类

import java.util.Arrays;

public class ConcatenateNumber implements Comparable<ConcatenateNumber>{
    private int num;
    private String string;

    public ConcatenateNumber(int num) {
        this.num = num;
        this.string = String.valueOf(num);
    }

    public String getString() {
        return string;
    }

    @Override
    public int compareTo(ConcatenateNumber cn) {
        String string1 = this.string + cn.getString();
        String string2 = cn.getString() + this.string;
        return string1.compareTo(string2);
    }

    @Override
    public String toString() {
        return string;
    }

    public static int getMinConcatenatedNumber(int[] nums){
        ConcatenateNumber[] cns = new ConcatenateNumber[nums.length];

        for (int i = 0; i < nums.length; i++) {
            cns[i] = new ConcatenateNumber(nums[i]);
        }

        Arrays.sort(cns);
        String numAsString = "";
        for (ConcatenateNumber cn : cns) {
            numAsString += cn.toString();
        }
        return Integer.valueOf(numAsString);
    }
}

测试代码

        int[] nums = new int[]{3,32,321};
        int concatenateNum = ConcatenateNumber.getMinConcatenatedNumber(nums);
        System.out.println(concatenateNum);