题目

核心思路

这道题很明显是一道排序相关的题，那么如何去比较两个数就比较重要了，只要找出两个数的比较方法，然后套到排序算法里就可以了，这也正是官方题解给出的思路，通过实现一个Comparator接口的类重写比较两个String类型的大小即可，而compare函数之中，一种很直接的方法就是假设两个字符串 a 和 b ，a + b 与 b + a 直接比较大小即可，由此可以得到如下的重写：

private class LargerNumberComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            String order1 = a + b;
            String order2 = b + a;
           return order2.compareTo(order1);
        }
}

这样就可以调用系统Arrays工具类中的sort方法，从而实现排序，然后依次输出并排除0即可。

下面说一下我的想法，看到这里要一位一位的比较数的大小，我第一个反应就是使用基数排序，从个位一直到最高位进行排序，不过这里题目并没有说具体每个数有多少位，而且数的位少的不一定就小于位多的，所以在基数排序进行分散收集的时候不存在的位就不是很好处理，我们来考虑下边的几个例子。

示例一

以下3个数在连接的时候的大小：
3、32、34
最大的可能就是[34, 3, 32]组成的 34332
这样比较之后发现，似乎3和33应该是等价的，也就是考虑它不存在的位应该用3进行替代分散，不过这是不是一般的呢？

示例二

以下3个数在连接时候的大小：
12、1213、121
这时候一下就变得复杂了，不过还是可以看出最大的组合为[1213, 12, 121]组成的121312121
这又是怎么得来的呢。首先看121，他如果在前边的话，只能后边接1213或者12，都是1开头，也就是这里的121相当于与1211等大，所以他要比1213小。然后来看12，他与其他的连接都是12开头，也就是这里它相当于与1212等大，所以他比1213小，比121大。那么我们就可以据此运算，假设遍历到下标i位进行分散的时候，如果当前要分散的数的位数len比i要小(或等于)，那么就应该用下标为i % len，来代替不存在的位，就像上边的12可以是121212121212...进行补位比较。不过这里还有一个问题，可以看下边的示例给出解答。

示例三

以下2个数在连接时候的大小：
12、121 以及这两个数 121、12
可能有人觉得这不是和上边的例子一样吗，就换了个顺序。不过这个例子里少了一个1213也就是4位长度的数。因为之前我说基数排序分散的时候要从最低位一直到最高位进行分散，这里最高的位数为3，也就是说相当于这两个数比较的时候都要考虑3位，那么根据上边的方法，12可以变成121，用i % len = 0位进行替代，这时候就会发现12和121变成等大的了，由于基数排序是稳定的，等大的两个数的顺序不会改变，经过分散收集之后得到的两个答案分别为12121和12112，这就出现问题了，因为这两个数根本不是等大的，真正跟12等大的应该是1212这样的。
那这里就必须考虑长度的问题了，能比较出两个数是否等大的最小长度就应该是这两个数的长度之和，也就是说对于上边的两个数，我们按照5位的长度进行比较，就一定可以得到正确的大小结果：12121与12112，不过既然用的是基数排序，从最低位到最高位，那么最高位就应该是两个最高位的和，所以提前遍历一遍数组找到最大的2个数，把最高位设置为这两个数长度的和，然后进行基数排序即可。基数排序可以参考百度搜索出的代码。

完整代码

class Solution {
    public String largestNumber(int[] nums) {
        if (nums == null || nums.length == 0) {
            return "";
        }

        int maxLen = 0;
        int secondLen = 0;
        int secondNum = 0;
        int maxNum = 0;

        // 将数字全部转换为字符串
        String[] numsToString = new String[nums.length];
        for (int i = 0; i < nums.length; i++) {
            numsToString[i] = Integer.toString(nums[i]);
        }

        for (int i = 0; i < nums.length; i++) {
            if (maxNum < nums[i]) {
                secondNum = maxNum;
                secondLen = maxLen;
                maxNum = nums[i];
                maxLen = numsToString[i].length();
            } else if (secondNum < nums[i]) {
                secondNum = nums[i];
                secondLen = numsToString[i].length();
            }
        }
        // 创建桶
        HashMap<Integer, LinkedList<String>> bucket = new HashMap<Integer, LinkedList<String>>();
        for (int i = 0; i < 10; i++) {
            bucket.put(i, new LinkedList<String>());
        }
        // 遍历所有位置的字符，利用桶子排序
        for (int i = maxLen + secondLen - 1; i >= 0; i--) {
            // 分散
            for (int j = 0; j < numsToString.length; j++) {
                int len = numsToString[j].length();
                char c = i >= len ? numsToString[j].charAt(i % len) : numsToString[j].charAt(i);
                bucket.get(c - '0').addLast(numsToString[j]);
            }
            // 收集
            int index = 0;
            for (int j = 9; j >= 0; j--) {
                LinkedList<String> temp = bucket.get(j);
                for (String s : temp) {
                    numsToString[index++] = s;
                }
                temp.clear();
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < numsToString.length; i++) {
            sb.append(numsToString[i]);
        }
        String res = sb.toString();
        return res.charAt(0) == '0' ? "0" : res;
    }
}

代码虽然有点长，但是还是比较简单的，而且效率也挺高的。最后那里使用StringBuilder进行组合字符串可以提高效率，另外返回结果的时候要注意00000这种情况，应该返回0而不是一串。如果文章有错误的地方还请指出，感谢阅读。感恩相遇~