算法17 Largest Number

题目：
给定一个非负整数列表，排列它们，使它们成为最大的数字。

例如，给定的[3, 30, 34, 5, 9]，最大的形成数量是9534330。

注意：结果可能非常大，所以您需要返回一个字符串而不是一个整数。

思路：最开始看到题目，会想将个位上较大的放在前面，个位相同再看十位，但是每个数字位数不确定，这样感觉思路不通。借鉴leetcode官方解法，大体思路就是，将int数组转换成string数组之后，通过两两字符串连接在一起后比较哪个更大，哪个字符串应该放在前面。

代码：

public static String largestNumber(int[] num) {
    if(num == null || num.length == 0)
        return "";

    // 转换成字符串数据，准备比较
    String[] s_num = new String[num.length];
    for(int i = 0; i < num.length; i++)
        s_num[i] = String.valueOf(num[i]);

    // 重写compare，判断两个字符串哪个应该在前面。
    Comparator<String> comp = new Comparator<String>(){
        @Override
        public int compare(String str1, String str2){
            String s1 = str1 + str2;
            String s2 = str2 + str1;
            return s2.compareTo(s1); // reverse order here, so we can do append() later
        }
    };

    Arrays.sort(s_num, comp);
    //排除都为0的特殊情况
    if(s_num[0].charAt(0) == '0')
        return "0";

    StringBuilder sb = new StringBuilder();
    for(String s: s_num)
        sb.append(s);

    return sb.toString();

}

空间复杂度O(n)
时间复杂度
输入数组的长度是n，
snum中字符串的平均长度是k，
然后，比较两个字符串会取O(k)。
排序需要O(nlgn)
添加到StringBuilder的应用程序需要O(n)。
所以总的是O(nklgnk)+O(n)=O(nklgnk)