题解 | #最大数#

思路：

1.把int数组转为String数组
2.对String数组排序，需要重写compare()方法。
1）当21和2比较时，按理21比2大，组合为212，但实际221更大。因此当字符之间比较时，如果一个字符包含于另一个字符，则被包含的字符放在前面。即2被21包含，2在21前面。
3.需要注意"0"+"0"+"0"组合后应该是"0"，而不是"000"。

方法一：冒泡排序法
具体做法：
使用冒泡排序法，依次比较前后两个数，转化成string后相连的大小，排成由大到小的组合。

class Solution {
public:
    string solve(vector<int>& nums) {
        for(int i = 0; i < nums.size(); i++){ //冒泡法
            for(int j = 1; j < nums.size(); j++)
                if(to_string(nums[j]) + to_string(nums[j - 1]) > to_string(nums[j - 1]) + to_string(nums[j])){
                    int temp = nums[j];
                    nums[j] = nums[j - 1];
                    nums[j - 1] = temp;
                }                    
        }
        string res = "";
        for(int i = 0; i < nums.size(); i++)  //遍历排序后的数组
            res += to_string(nums[i]);
        if(res[0] == '0')   //当第一位数就是0时，整个最大也为0。去掉重复的0
            return "0";
        return res;
    }
};

复杂度分析：

时间复杂度： ，冒泡排序两层循环
空间复杂度： ，没有使用额外空间

方法二：重载sort函数
具体做法：
另写一个比较函数来重载sort的排序规则，规则是将两数转变成string后，相加比较大小。
复杂度分析：

时间复杂度： ，sort函数属于快排，复杂度为O(n)
空间复杂度： ，没有使用额外的空间

import java.util.*;


public class Solution {
    /**
     * 最大数
     * @param nums int整型一维数组 
     * @return string字符串
     */
    public String solve (int[] nums) {

        if (nums == null || nums.length == 0) {
            return null;
        }

        ArrayList<String> list = new ArrayList<>();

        for (Integer a : nums) {
            list.add(String.valueOf(a));
        }

        list.sort(new Comparator<String> () {

            @Override
            public int compare (String o1, String o2) {
                return (o2 + o1).compareTo(o1 + o2);
            }
        });

        if (list.get(0).equals("0")) {
            return "0";
        }

        StringBuilder sb = new StringBuilder();
        for (String s : list) {
            sb.append(s);
        }

        return sb.toString();
    }
}