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

题目

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

示例 1:

输入: [10,2]
输出: “102”

示例 2:

输入: [3,30,34,5,9]
输出: “3033459”

提示:

0 < nums.length <= 100
说明:

输出结果可能非常大，所以你需要返回一个字符串而不是整数
拼接起来的数字可能会有前导 0，最后结果不需要去掉前导 0

思路

看到题目第一反应这不就是先将数字转为字符串，然后按字典序排序，拼接起来就好了嘛。

但是一用类库排序一试并不对，有一种情况会出错，比如类似和，的字典序大，但是这个题中应该排在的前面，因为’’‘’比’’‘’更小，所以还是要另想办法。

那既然比小，意味着决定两个数哪个在前的因素是拼接的顺序，可以推测对于和两个字符串，如果小于的字典序，那么就应该放在前面。举个例子，还是对于#card=math&code=30%28%E8%AE%B0%E4%BD%9Ca%29&id=Ot1uM)和#card=math&code=3%28%E8%AE%B0%E4%BD%9Cb%29&id=rArLy)，因为#card=math&code=303%28a%2Bb%29&id=u0tGx)小于#card=math&code=330%28b%2Ba%29&id=L0FcE)，所以要放在前面。那这个排序规则是不是对于多个字符串也成立呢，即是不是具有传递性，如果a<b，b<c，是否一定有a<c呢，举几个例子倒是成立，不过严谨的证明也不简单，「这里」有人给出了证明。

代码

class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(arr, (a, b) -> (a + b).compareTo(b + a));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(arr[i]);
        }
        return sb.toString();
    }
}