### 题目

Given a list of non negative integers, arrange them such that they form the largest number.

For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.

Note: The result may be very large, so you need to return a string instead of an integer.

### 自己写排序算法

#### 代码

public class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
int[][] memo = new int[nums.length][nums.length];
sort(strs,0,strs.length-1,memo);
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str);
}
}

public void sort(String[] nums, int lo, int hi, int[][] memo) {
if (lo == hi) { return; }
int mid = lo + (hi - lo) / 2;
sort(nums,lo,mid,memo);
sort(nums,mid+1,hi,memo);
merge(nums,lo,mid,mid+1,hi,memo);
}
public void merge(String[] nums, int lo1, int hi1, int lo2, int hi2, int[][] memo) {
String[] temp = new String[hi2-lo1+1];
int cur = 0, cur1 = lo1, cur2 = lo2;
while (cur1 <= hi1 && cur2 <= hi2) {
int ret = compare(nums,cur1,cur2,memo);
temp[cur++] = (ret >= 2)? nums[cur1++] : nums[cur2++];
}
while (cur1 <= hi1) { temp[cur++] = nums[cur1++]; }
while (cur2 <= hi2) { temp[cur++] = nums[cur2++]; }
for (int i = 0; i < temp.length; i++) {
nums[lo1+i] = temp[i];
}
}
/*
* return:
*  1: num1 < num2
*  2: num1 == num2
*  3: num1 > num2
*/
public int compare(String[] nums, int pos1, int pos2, int[][] memo) {
if (memo[pos1][pos2] > 0) { return memo[pos1][pos2]; }
String sum1 = nums[pos1] + nums[pos2];
String sum2 = nums[pos2] + nums[pos1];
for (int i = 0; i < sum1.length(); i++) {
char c1 = sum1.charAt(i);
char c2 = sum2.charAt(i);
if (c1 > c2) {
memo[pos1][pos2] = 3;
return 3;
} else if (c1 < c2){
memo[pos1][pos2] = 1;
return 1;
}
}
memo[pos1][pos2] = 2;
return 2;
}
public String trimLeadingZero(String s) {
int cur = 0;
while (cur < s.length() && s.charAt(cur) == '0') { cur++; }
s = s.substring(cur);
return (s.isEmpty())? "0" : s;
}
}


### 用库函数Arrays.sort()

#### 代码

public class Solution {
public String largestNumber(int[] nums) {
String[] strs = new String[nums.length];
for (int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
int[][] memo = new int[nums.length][nums.length];
Arrays.sort(strs, new Comparator<String>() {
public int compare(String s1, String s2) {
String sum1 = s1 + s2;
String sum2 = s2 + s1;
return sum2.compareTo(sum1);
}
});
StringBuilder sb = new StringBuilder();
for (String str : strs) {
sb.append(str);
}