剑指offer一刷：排序

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

难度：中等

此题求拼接起来的最小数字，本质上是一个排序问题。设数组 nums 中任意两数字的字符串为 x 和 y，则规定排序判断规则为：

• 若拼接字符串 x + y > y + x，则 x“大于”y；
• 反之，若 x + y < y + x，则 x“小于”y；

$x$“小于”y 代表：排序完成后，数组中 x 应在 y 左边；“大于”则反之。

根据以上规则，套用任何排序方法对 $ms$ 执行排序即可。

采用快速排序的方法：

class Solution {
    public String minNumber(int[] nums) {
        String[] strs = new String[nums.length];
        for(int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        quickSort(strs, 0, strs.length - 1);
        StringBuilder res = new StringBuilder();
        for(String s : strs)
            res.append(s);
        return res.toString();
    }
    void quickSort(String[] strs, int l, int r) {
        if(l >= r) return;
        int i = l, j = r;
        String tmp = strs[i];
        while(i < j) {
            while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
            while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
            tmp = strs[i];
            strs[i] = strs[j];
            strs[j] = tmp;
        }
        strs[i] = strs[l];
        strs[l] = tmp;
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }
}

作者：Krahets
链接：https://leetcode.cn/leetbook/read/illustration-of-algorithm/59ceyt/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

时间复杂度：O(NlogN)，空间复杂度：O(N)。

注意：

1. j 和 i 的顺序，谁先谁后
2. 2 个 while 中的判断条件，等号最好都带上（绝对不能都不带）