题目描述

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

样例

输入: [10,2]
输出: 210

输入: [3,30,34,5,9]
输出: 9534330

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

算法分析

贪心 + 排序

• 1、对于两个数字a,b进行拼接，比较a + b 和 b + a的大小，将拼接后偏大的数字对应的数字顺序放置数字，例如若a + b > b + a，则对于数字a,b，则将a放置b的前面
• 2、扩展到所有数字，则通过1的思想可以将所有的数字对于两个的拼接的大小情况，通过某种规则进行进行排序，从大到小放置对应的数字
• 3、枚举排序后的结果，将所有的数字依次拼接到ans后面
• 4、注意特殊情况：全0情况，需要将前导0全部去除，保留最后一个0

时间复杂度 $O(nlogn)$

Java 代码

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] s = new String[n];
        for(int i = 0;i < n;i ++) s[i] = nums[i] + "";
        Arrays.sort(s, (a, b) -> {
            String x = "" + a + b ;
            String y = "" + b + a ;
            return y.compareTo(x);
        });

        StringBuilder ans = new StringBuilder();
        for(int i = 0;i < s.length;i ++)
        {
            ans.append(s[i]);
        }
        String res = ans.toString();
        //处理前面全是0的情况
        int k = 0;
        while(k < n - 1 && res.charAt(k) == '0') k ++;
        return res.substring(k);
    }
}