【题目】
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.
Credits:Special thanks to
@ts for adding this problem and creating all test cases.
【题意】
给定一个数组，这些数连在一起可以组成一个大数，求能组成最大数。
如 [3, 30, 34, 5, 9] 能组成的最大数为 9534330。
由于组成的数可能非常大，用字符串返回。
【解法】
//不想听繁琐分析的课跳过直接看代码，代码中有注释
关键是确定每个数在最后结果中的先后位置，比较直观的是个位数越大的越靠前，如例子中9在5, 4, 3之前；
个位相同的再看十位，如例子中34应当在30之前；
难点是位数不等时，先后关系怎么确定？如例子中3应当放在30和34之前、之后还是中间？
结果是3放在了34和30中间，为什么呢？这是因为十位上的4比个位上3大，所以34在3之前，而十位上的0比个数上的3小，所以30在3之后。
这样貌似可以找到规律，就是对于那些有包含关系的数，如1234包含12，那么只需看1234比12多出的部分34比12大还是小。
通过这样的方法，貌似也可判断出个先后顺序。只是这样需要考虑的情况太复杂了，如565656和56……
//正解如下：
可以换一下思路，要想比较两个数在最终结果中的先后位置，何不直接比较一下不同组合的结果大小？
举个例子：要比较3和34的先后位置，可以比较334和343的大小，而343比334大，所以34应当在前。
这样，有了比较两个数的方法，就可以对整个数组进行排序。然后再把排好序的数拼接在一起就好了。
public class Solution {
/*
* @param nums: A list of non negative integers
* @return: A string
*/
public String largestNumber(int[] nums) {
// write your code here
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++) {
strs[i] = Integer.toString(nums[i]);
}
Arrays.sort(strs, new Cmp());
StringBuilder sb = new StringBuilder();
for(int i = 0; i < strs.length; i++) {
sb.append(strs[i]);
}
String result = sb.toString();
int index = 0;
while(index < result.length() && result.charAt(index) == '0') {
index++;
}
if(index == result.length()) {
return "0";
}
return result.substring(index);
}
}
class Cmp implements Comparator<String>{
@Override
public int compare(String a, String b) {
String ab = a.concat(b);
String ba = b.concat(a);
return ba.compareTo(ab);
}
}
