☆打卡算法☆LeetCode 179. 最大数 算法解析

大家好，我是小魔龙，Unity3D软件工程师，VR、AR，虚拟仿真方向，不定时更新软件开发技巧，生活感悟，觉得有用记得一键三连哦。

一、题目

1、算法题目

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

2、题目描述

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

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

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

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

二、解题

1、思路分析

这道题要求重新排列每个数的顺序组成最大整数，可以逐个比较数组的中数值，将较大的数值放到前面。

比如：[45,56,81,76,123] ，结果:"81765645123"。

但是，数组中有相同数字开头的情况，比如[4,42]和[4,45]:

• 对于[4,42]，比较442>424，需要把4放前面
• 对于[4,45]，比如445<454，需要把45放前面

对于这种在排序前无法确定两个数谁大的情况应该怎么排序的？

这种情况就可以根据不同的排序 结果 来决定两个数的排序关系：

• 如果结果，ab>ba，则需要将a放在b前面
• 如果结果，ab

2、代码实现

代码参考：

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;
        String[] ss = new String[n];
        for (int i = 0; i < n; i++) ss[i] = "" + nums[i];
        Arrays.sort(ss, (a, b) -> {
            String sa = a + b, sb = b + a ;
            return sb.compareTo(sa);
        });
        StringBuilder sb = new StringBuilder();
        for (String s : ss) sb.append(s);
        int len = sb.length();
        int k = 0;
        while (k < len - 1 && sb.charAt(k) == '0') k++;
        return sb.substring(k);
    }
}

3、时间复杂度

时间复杂度：O(n²)

由于是对String进行排序，当排序对象不是Java中基本数据类型时，不会使用快排，Arrays.sort()底层会使用插入排序，那么时间复杂度就是O(n²)。

空间复杂度：O(n)

其中n是数组的长度。

三、总结

总结来说解题思路就是：

• 转成字符串数组
• 两两比较字符串中的元素的大小
• 以结果为导向，确定哪个元素在前面
• 输出结果