Leetcode No.179 最大数

一、题目描述

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

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

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

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

示例 3：

输入：nums = [1] 输出："1"

示例 4： 输入：nums = [10] 输出："10"

二、解题思路

要想组成最大的整数，一种直观的想法是把数值大的数放在高位。于是我们可以比较输入数组的每个元素的最高位，最高位相同的时候比较次高位，以此类推，完成排序，然后把它们拼接起来。这种排序方式对于输入数组 没有相同数字开头 的时候是有效的，例如 [45,56,81,76,123]。

下面考虑输入数组 有相同数字开头 的情况，例如 [4,42]和 [4,45]。

对于 [4,42]，比较442>424，需要把 4 放在前面； 对于 [4,45]，比较445<454，需要把 45 放在前面。 因此我们需要比较两个数不同的拼接顺序的结果，进而决定它们在结果中的排列顺序。

由于需要拼接以后才能决定两个数在结果中的先后顺序，N 个数就有 N!种拼接的可能，我们是不是需要先得到 N个数的全排列以后，再选出最大的呢？答案是没有必要。上述排序规则满足传递性，两个元素比较就可以确定它们在排序以后的相对位置关系。

三、代码

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        StringBuilder rs = new StringBuilder();
        String[] array = new String[n];
        for(int i = 0;i < n;i++) 
            array[i] = String.valueOf(nums[i]);
            Arrays.sort(array, new Comparator<String>() {
                @Override
                public int compare(String o1, String o2) {
                    return (o2+o1).compareTo(o1+o2);
                }
            }
        );
        for(int i = 0;i < n-1;i++) {
            if(!(rs.length() == 0 && "0".equals(array[i]))){
                rs.append(array[i]);
            }
        }
        return rs.append(array[n-1]).toString();
    }
}

四、复杂度分析

时间复杂度：O(nlognlogm)，其中 n 是给定序列的长度，m 是 32位整数的最大值，每个数转化为字符串后的长度是 O(logm) 的数量级。排序比较函数的时间复杂度为 O(logm)，共需要进行 O(nlogn) 次比较。同时我们需要对字符串序列进行拼接，时间复杂度为O(nlogm)，在渐进意义上小于 O(nlognlogm)。

我们也可以对排序比较函数进行优化，如预处理出数组每一个数的大于它的最小的十的整次幂，这样可用将时间复杂度降低到 O(nlogn)，但这样会使得空间复杂度上升到 O(n)。我们也可以使用数学方法加速计算整次幂，如二分计算等，但这种优化常数较大，最终耗时不一定更短。 空间复杂度：O(logn)，排序需要O(logn) 的栈空间。