把数组排成最小的树

把数组排成最小的树

题目描述：

输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个

题解：

刚看见这道题目时，脑子里想的是通过排序解决，刚开始想的是，根据int数组内每个数字的个十百位分别进行比较排序，然后发现每个数字的位数并不相同，如果想要进行比较排序，可以将其转换成String数组进行排序。不过，通过题目描述可以发现，需要将数字拼接然后比较大小，所以可以重写比较器。

第一步：将int数组转成String数组

        String[] str = new String[nums.length];
        for (int i = 0; i < str.length; i++) {
            str[i] = String.valueOf(nums[i]);
        }

第二步：重写比较器进行排序

Arrays.sort(str, new Comparator() {
            @Override
            public int compare(String o1, String o2) {
                return (o1 + o2).compareTo(o2 + o1);
            }
        });

重写的比较器是将o1和o2分别进行拼接，然后比较大小，最终以升序的方式进行排序。

 比如上图中，原始数组是[2，123]，转化成字符串，然后拼接进行比较，则有”2123“、”1232“。在字符串的compareTo方法中，长度相同的情况下，主要比较的是第一个不相同的字母，显然‘2’>'1'。最终通过字符串比较排序，得到["123","2"]的排序。

当然，因为Comparator时接口类型，所以，这里也可以直接使用lambda表达式：

        Arrays.sort(str, (o1,o2) ->{
                return (o1 + o2).compareTo(o2 + o1);
            }
        );

第三步：将排序后的字符串数组拼接，然后返回

        StringBuffer res = new StringBuffer();
        for (int i = 0; i < str.length; i++) {
            res.append(str[i]);
        }
        return res.toString();

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