179. 最大数

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。

注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

示例 1：

输入：nums = [10,2]
输出："210"

示例 2：

输入：nums = [3,30,34,5,9]
输出："9534330"

提示：

• 1 <= nums.length <= 100
• 0 <= nums[i] <= 10^9

调用排序函数，巧定排序规则

步骤：

1. 将整数数组 nums 转换成字符串数组strs，因为后续需要进行字符串的拼接和比较操作。
2. 巧定排序规则，在 Arrays.sort(strs, (x,y) -> f(x,y)) 中，如果 f(x,y) > 0，则说明 x > y，即 y 在 x 的前面。因此为了让大数在前面，我们需要设计一个映射f， 满足当 x < y 时，f(x,y) > 0，很明显，我们可以用 f(x,y) = y - x，但是x和y是字符串，不能这么做，所以我们只能用 f(x,y) = (y+x).compareTo(x+y)。
3. 排完序后，要检查第一个元素是否为"0"，如果是，则整个数组都是0，直接返回"0"。否则把字符数组拼接成字符串并返回。

细节：

1. 判空
2. 结果数组可能为 0，这时候直接返回一个 0，不要拼接多个 0.

class Solution {
    public String largestNumber(int[] nums) {
        // 将整数数组nums转换成字符串数组strs，因为后续需要进行字符串的拼接和比较操作。
        String[] strs = new String[nums.length];
        for (int i = 0; i < nums.length; i++)
            strs[i] = String.valueOf(nums[i]);
        
        // 将两个字符串x和y进行拼接（即y+x和x+y），然后比较这两个拼接后的字符串。如果y+x比x+y大，
        // 说明在最终组合的数字中，y应该放在x的前面，即把大的放在前面，这样排序后的数组能够组成最大的数字。
        // 如果(y + x).compareTo(x + y)的结果大于0，则意味着字符串yx的字典序大于xy的字典序，
        // 按照这个比较器的定义，x>y，因此y应该排在x之前。
        // 默认升序，所以如果x>y，则y在x前。
        Arrays.sort(strs, (x, y) -> (y + x).compareTo(x + y));
        
        // 排序后，如果数组的第一个元素是"0"，那么整个数组都是0。因为即使有非零数字，它们也会根据排序规则被放在"0"的后面。在这种情况下，直接返回"0"。
        if (strs[0].equals("0"))
            return "0";
        StringBuilder res = new StringBuilder();
        for (String s : strs)
            res.append(s);

        return res.toString();
    }
}

• 时间复杂度：O(n log n * log m)，其中 n 是给定序列的长度，m 是 32 位整数的最大值，每个数转化为字符串后的长度是 O(log m) 的数量级。 排序中的比较函数的时间复杂度为 O(log m)（因为要比较log m个字符），共需要进行 O(nlog n) 次比较。最后我们需要对字符串序列进行拼接，时间复杂度为 O(nlog m)， 因此总的时间复杂度为 O(n log n * log m + n log m)，在渐进意义上小于 O(n log n * log m)。
• 空间复杂度：排序需要 O(log n) 的栈空间。

手写快速排序，巧定排序规则

步骤：

1. 把整数数组 nums 转换成字符串数组strs，因为后续需要进行字符串的拼接和比较操作。
2. 采用快速排序算法对字符串数组strs进行排序。
   • 选择数组的第一个元素作为基准元素。
   • 双指针遍历字符串数组，将字典序小于等于基准元素的字符串放在基准元素的左边，字典序大于基准元素的字符串放在基准元素的右边。
   • 一次遍历可以确定 pivot 的位置，然后递归地对左右两个子数组进行快速排序。
3. 排完序后，要检查第一个元素是否为"0"，如果是，则整个数组都是0，直接返回"0"。否则把字符数组拼接成字符串并返回。

细节：

1. 判空
2. 快速排序时注意左右指针的先后顺序
3. 结果数组可能为 0，这时候直接返回一个 0，不要拼接多个 0.

class Solution {
    // 交换数组中的两个元素
    private void swap(String[] strs, int i, int j) {
        String temp = strs[i];
        strs[i] = strs[j];
        strs[j] = temp;
    }

    void quickSort(String[] strs, int l, int r) {
        if (l >= r) return;
        int i = l, j = r;
        // 暂存基准元素，这里选择第一个元素作为基准元素。
        String pivot = strs[l];
        
        // 当左右指针未相遇时，进行分区操作。循环结束后 pivot 左边都是字典序比 pivot 小或等的元素，右边都是字典序比 pivot 大的元素。
        while (i < j) {
            // 一定要让 j 在 i 前面，这样结束时，j--，即 i = j 指向最后一个字典序小于等于基准值的元素，
            // 这样再和基准值交换就不会错。本质是我们取了最左侧的元素作为基准值。
            // 从数组的右端开始向左扫描，找到第一个使得 strs[j] + pivot 的字典序小于等于 pivot + strs[j] 的元素。
            while ((strs[j] + pivot).compareTo(pivot + strs[j]) > 0 && i < j) j--;
            // 从数组的左端开始向右扫描，找到第一个使得 strs[i] + pivot 的字典序大于 pivot + strs[i] 的元素。
            while ((strs[i] + pivot).compareTo(pivot + strs[i]) <= 0 && i < j) i++;
            swap(strs, i, j);
        }
        
        // 分区结束后，i 和 j 相遇，此时将基准元素与相遇点的元素交换，确保基准元素归位至最终排序后的正确位置。
        swap(strs, l, i);
        // 对基准元素左侧和右侧的子数组递归执行快速排序。
        quickSort(strs, l, i - 1);
        quickSort(strs, i + 1, r);
    }

    public String largestNumber(int[] nums) {
        // 把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();
        // 注意这里判断的是最后一个元素，这是由快速排序中的规则决定的
        if (strs[strs.length - 1].equals("0"))
            return "0";
        // 注意，这里是从后往前遍历，这是由快速排序中的规则决定的
        for (int i = strs.length - 1; i >= 0; i--)
            res.append(strs[i]);
        return res.toString();
    }
}

复杂度同方法一。