🖐贪心 - [NC]111. 最大数、最小数 - 《LeetCode》

题目
解题思路：最大数
解题思路：最小数
- 复杂度分析
- 我的代码

题目

给定一组非负整数 $[NC]111. 最大数、最小数 - 图1$ ，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

解题思路：最大数

对于 [NC]111. 最大数、最小数 - 图2 中的任意两个值 [NC]111. 最大数、最小数 - 图3 和 [NC]111. 最大数、最小数 - 图4 ，我们无法直接从常规角度上确定其 大小 / 先后 关系。
但我们可以根据「结果」来决定 [NC]111. 最大数、最小数 - 图5 和 [NC]111. 最大数、最小数 - 图6 的排序关系：

如果拼接结果要比大，那么我们会认为应该放在前面。

另外，注意我们需要处理前导零（最多保留一位）。

解题思路：最小数

对于 [NC]111. 最大数、最小数 - 图11 中的任意两个值 [NC]111. 最大数、最小数 - 图12 和 [NC]111. 最大数、最小数 - 图13 ，我们无法直接从常规角度上确定其 大小 / 先后 关系。
但我们可以根据「结果」来决定 [NC]111. 最大数、最小数 - 图14 和 [NC]111. 最大数、最小数 - 图15 的排序关系：

如果拼接结果要比小，那么我们会认为应该放在前面。

另外，注意我们需要处理前导零（最多保留一位）。
[NC]111. 最大数、最小数 - 图20

复杂度分析

时间复杂度： [NC]111. 最大数、最小数 - 图21 ，其中 [NC]111. 最大数、最小数 - 图22 是数组的长度。

  - 由于是对 ![](https://cdn.nlark.com/yuque/__latex/259a6ebbaa3baa5366c9042f06fc1d16.svg#card=math&code=%5Ctext%7BString%7D&id=dfluz) 进行排序，当排序对象不是 ![](https://cdn.nlark.com/yuque/__latex/45f84fd314c0f63359252571e93dd74e.svg#card=math&code=%5Ctext%7BJava%7D&id=JiUDd) 中的基本数据类型时，不会使用**快排**（考虑排序稳定性问题）。![](https://cdn.nlark.com/yuque/__latex/42762354f93ebd8e2b05e6323aa393a5.svg#card=math&code=%5Ctext%7BArrays.sort%28%29%7D&id=gvCWC)** **的底层实现会**「元素数量/元素是否大致有序」**决定是使用**插入排序**还是**归并排序**，这里直接假定使用的是**「插入排序」，**故而时间复杂度是  ![](https://cdn.nlark.com/yuque/__latex/bf7c2e3ac858e1c3496fd2f47a300139.svg#card=math&code=%5Csmall%20O%28n%29&id=a5xsN) 。

空间复杂度： [NC]111. 最大数、最小数 - 图23

我的代码


public class Solution {
    public  String largestNumber(int[] nums) {
        String[]strings=new String[nums.length];
        for (int i=0;i<nums.length;i++){
            strings[i]=nums[i]+"";
        }
        //o2+o1 > o1+o2 则o2放前面
        Arrays.sort(strings, new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                String a=o1+o2;
                String b=o2+o1;
                return b.compareTo(a);
            }
        }); 
        if(strings[0].equals("0"))return "0";
        StringBuffer res=new StringBuffer();
        for (int i=0;i<nums.length;i++){
            res.append(strings[i]);
        }
        return res.toString();
    }
}