一、题目描述

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

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

示例 1：

输入：nums = [10,2]
输出：“210”

示例 2：

输入：nums = [3,30,34,5,9]
输出：“9534330”

二、代码思路

整体思路：本质上属于自定义排序比较规则，然后按照规则进行排序，最终组成结果值。

根据整体的思路，有三种方法定义排序规则。

1. 设字符串 A 与 B，比较C1=A+B转成整形与C2=B+A转成整形两者谁大从而判断A与B的顺序。缺点就是整形会越界。
   （0 <= nums[i] <= 109）
2. 与第一个思路类似，但是这次不需要转整形，而是遍历C1与C2字符串来逐个字符判断大小。
3. 与2类似也是两个字符串比较，2是最简单的比较。

三、代码题解

public String largestNumber(int[] nums) {//考虑一种边界值，就是所有元素都是0String strs[] = new String[nums.length];int flag = 0;for (int i = 0; i < nums.length; i++) {if (nums[i] != 0) {flag = 1;}strs[i] = nums[i] + "";}if (flag == 0) {return "0";}Arrays.sort(strs, new Comparator<String>() {@Overridepublic int compare(String o1, String o2) {if (compareStrs(o1, o2)) {return 1;} else {return -1;}}});//quickSort(nums, 0, nums.length - 1);StringBuffer stringBuffer = new StringBuffer();for (int i = strs.length - 1; i >= 0; i--) {stringBuffer.append(strs[i]);}return new String(stringBuffer);}//比较两个字符串谁比较大，但是会出现整形越界的情况public boolean compareStrs1(String str1, String str2) {int num1 = Integer.parseInt(str1 + str2);int num2 = Integer.parseInt(str2 + str1);return num1 >= num2 ? true : false;}//比较两个字符串谁比较大public boolean compareStrs(String str1, String str2) {String num1 = str1 + str2;String num2 = str2 + str1;int length = num1.length();for (int i = 0; i < length; i++) {if (num1.charAt(i) > num2.charAt(i)) {return true;} else if (num1.charAt(i) < num2.charAt(i)) {return false;} else {continue;}}return true;}

时间复杂度：O(n^2logn)
空间复杂度：O(n)