巧妙定义排序规则，以处理复杂的字符判定

题目链接-来源：力扣（LeetCode）

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

示例 1:

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

示例 2:

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

思路：

如果此题用类似 DFS 的方法暴力展开，会达到 O(n!) 的复杂度。
我们思考，如示例 2，’30’ 排在 ‘3’ 的前面，而 ‘3’ 又排在 ‘34’ 前面。那么说明存在一种规则，使得在这个规则下， ‘30’「小于」’3’「小于」’34’。我们只要能定义出这种规则，便可以利用任意一种 O(nlogn) 的排序方法解决此题。
题目要求构造出最小的数，显然，这样的数，我们应该让「较小」元素放到头部，而「较大」元素放到尾部。那么比较两个数之间的大小，最直观的方法就是，我们比较其组合后的数字大小，比如 数字 X 和数字 Y，若 XY < YX，我们称 X 「小于」 Y。
于是只要定义一个比较器 Comparator 实现此规则，即可以此排序，之后连接所有数字即可。

时间复杂度：O(nlogn)
空间复杂度：O(n)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public String minNumber(int[] nums) {
        int n = nums.length;
        String[] numsS = new String[n];
        for (int i = 0; i < n; i++) {
            numsS[i] = String.valueOf(nums[i]);
        }
        Arrays.sort(numsS, (x, y) -> (x + y).compareTo(y + x));
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(numsS[i]);
        }
        return sb.toString();
    }
}