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.
分析：给定一个正整数数组，将数组的数字整合成一个最大的数字。
样例：① [3, 30, 34, 5, 9]->9534330
②[121,12]->12121
③[0,0] -> 0
（1）将数组的数字组合，这隐含着一个大数问题，所以不可以直接用int或者long来保存结果，需要用到字符串（也可以用数组）.
（2）字符串m与字符串n拼接，可以成为mn或者nm。要比较mn与nm的大小，不能直接用Arrays.sort()函数，这个函数排序后的结果为升序，重写Comparator 实现降序，才能组成最大的数字。
(3)字符串m与n的大小比较规则：当mn>nm时，m>n；
当mn=nm时，m=n；
当mn<nm时，m<n；
(4)字符串的比较规则：str1="abcda";str2="abcdb";当比较到第五个字符str1为a，str2为b 。a的ASCII码小于b的ASCII码。所以str1<str2
下面的代码 直接使用 Arrays.sort(com, new Comparator<Object>() { .....});在sort函数中重写 Comparator<Object>()，效率略低。跑完leetcode上的样例需要334ms。
public String largestNumber(int[] nums) {
if (nums == null)
return null;
int len = nums.length;
String[] com = new String[len];
int all0 = ;
for (int i = ; i < len; i++) {
if (nums[i] == ) {
all0++;
System.out.println("~~~" + all0);
}
com[i] = Integer.toString(nums[i]);
}
Arrays.sort(com, new Comparator<Object>() {
public int compare(Object obj1, Object obj2) {
String str1 = (String) obj1;
String str2 = (String) obj2;
String com1 = str1 + str2;
System.out.println("com1:" + com1);
String com2 = str2 + str1;
System.out.println("com2:" + com2);
if (com1.compareTo(com2) >= ) {
System.out.println("com1<com2");
return -;
} else {
System.out.println("com1>com2");
return ;
}
}
});
String ans = "";
for (int i = ; i < len; i++) {
ans += com[i];
}
if (all0 == len)
ans = "";
return ans;
}做出以下改进 拍完样例的时间为120ms
Comparator<String> comp = new Comparator<String>() {
@Override
public int compare(String str1, String str2) {
String s1 = str1 + str2;
String s2 = str2 + str1;
return s2.compareTo(s1);
// reverse order here, so we can do append() later
}
};
Arrays.sort(com, comp);