题目

• 给定一个数组存储的是非负数字，将其重排形成一个最大的数字
• 举例，输入input[10, 2]，输出"210",为了防止数字拼接溢出，返回字符串形式
  

解题方法

• 给定的数组我们要判定其组成的数据最大，我们就需要按照数组按照一定顺序排列，保证其顺序，然后遍历拼接即可形成最终结果
• 那么数组的排序应该采用什么方式为准则呢：假设有数字num1和num2然后按照num1+num2拼接成字符串s1，以及nums2+num1拼接为s2(+表示字符串拼接),然后分别按位进行s1和s2的比较，找出比较大的那个，根据我们的代码需求返回true or false
• 既然排序规则确定了，还有影响该程序时间复杂度最重要的一点就是采用的排序方法，我的代码中试过了冒泡和插入排序，虽然理论上都是O(n^2)时间复杂度，但是插入排序程序运行时间要低一些，空间复杂度O(1)
• 官方给出的就是将源数组生成字符串然后比较重写形成结果，其时间复杂度O(nlogn)，空间复杂度O(n)

源代码

class Solution {
    public String largestNumber(int[] nums) {
        String result = "";
        for (int i = 0; i < nums.length; i++) {
            int max = i;
            for (int j = i; j < nums.length; j++) {
                if (cmp(nums[max], nums[j])) max = j;
            }
            exch(nums, max, i);
        }
        for (int i = nums.length-1; i >= 0; i--) {
            result += String.valueOf(nums[i]);
        }
        if (result.charAt(0) == '0' && result.charAt(result.length()-1) == '0') return "0";
        return result;
    }
    
    private static boolean cmp (int num1, int num2) {
        String s1 = String.valueOf(num1) + String.valueOf(num2);
        String s2 = String.valueOf(num2) + String.valueOf(num1);
        for (int i = 0; i < s1.length(); i++) {
            if (Integer.parseInt(s1.substring(i, i+1)) > Integer.parseInt(s2.substring(i, i+1))) return true;
            if (Integer.parseInt(s1.substring(i, i+1)) < Integer.parseInt(s2.substring(i, i+1))) return false ;
        }
        return false;
    }
    
    private void exch(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}