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.

觀察一下這道題，第一位最大的數應該放在前頭，比如9應該放在前頭，5第二，那么3、30、34又該怎么處理呢？

最開始的想法就是一位一位比過去，比如30跟34。但是比如3跟30位數不同又該怎么比呢？我一開始以為3等同于33，所以34和30的后一位跟3比就好了

但是遇到這個情況824和8247，按我的理解824<8247，但是其實相反，因為8248247 > 8247824.

這才發現是要循環的，824挨個位數比完之后，要跳回8；8247也是，7這位比完之后，要跳回8。

所以就有如下挨個比的方法：(略笨)

 1 public class Solution { 2     public String largestNumber(int[] num) { 3         StringBuffer res = new StringBuffer(); 4         String[] str = new String[num.length]; 5         for (int i=0; i<num.length; i++) { 6             str[i] = Integer.toString(num[i]); 7         } 8         Comparator<String> comp = new Comparator<String>() { 9             public int compare(String t1, String t2) {10                 int i = 0;11                 int j = 0;12                 while (i != t1.length()-1 || j != t2.length()-1) {13                     if (t1.charAt(i) != t2.charAt(j)) {14                         return t1.charAt(i) - t2.charAt(j);15                     }16                     else {17                         i = (i + 1) % t1.length();18                         j = (j + 1) % t2.length();19                     }20                 }21                 return t1.charAt(i)==t2.charAt(j)? 0 : t1.charAt(i)-t2.charAt(j);22             }23         };24         Arrays.sort(str, comp);25         for (int j=str.length-1; j>=0; j--) {26             res.append(str[j]);27         }28         while(res.length() > 1 && res.charAt(0) == '0') { // delete front 029             res.deleteCharAt(0);30         }31         return res.toString();32     }33 }

聰明方法：其實干嘛要挨個比呢，按最直接的方法，接起來，誰大誰在前：

可以換一下思路，要想比較兩個數在最終結果中的先后位置，何不直接比較一下不同組合的結果大小？

舉個例子：要比較3和34的先后位置，可以比較334和343的大小，而343比334大，所以34應當在前。

這樣，有了比較兩個數的方法，就可以對整個數組進行排序。然后再把排好序的數拼接在一起就好了。

首先把int 全部轉換成string array，然后，自己寫一個comparator，判斷ab ba的大小，從而把a，b排序

然后把所有的連起來，記住，大的在后面，從后面開始連接。最后去掉前面的0；

 1 public class Solution { 2     public String largestNumber(int[] num) { 3         StringBuffer res = new StringBuffer(); 4         String[] str = new String[num.length]; 5         for (int i=0; i<num.length; i++) { 6             str[i] = Integer.toString(num[i]); 7         } 8         Comparator<String> comp = new Comparator<String>() { 9             public int compare(String t1, String t2) {10                 String t12 = t1 + t2;11                 String t21 = t2 + t1;12                 for (int i=0; i<t1.length()+t2.length(); i++) {13                     if (t12.charAt(i) != t21.charAt(i)) {14                         return t12.charAt(i) - t21.charAt(i);15                     }16                 }17                 return 0;18             }19         };20         Arrays.sort(str, comp);21         for (int j=str.length-1; j>=0; j--) {22             res.append(str[j]);23         }24         while(res.length() > 1 && res.charAt(0) == '0') { // delete front 025             res.deleteCharAt(0);26         }27         return res.toString();28     }29 }

別人的方法參考：思路相同，主要是參考他的comparator寫法

 1 public class Solution { 2     public String largestNumber(int[] num) { 3         if(num.length==0) return null; 4          5         String[] strs = new String[num.length]; 6         for(int i=0; i<num.length; i++){ 7             strs[i] = Integer.toString(num[i]); 8         } 9         10         Arrays.sort(strs, new myComparator());11         StringBuilder sb = new StringBuilder();12         for(int i=strs.length-1; i>=0; i--){13             sb.append(strs[i]);14         }15         16         int i=0; 17         while(i<strs.length && sb.charAt(i) == '0'){18             i++;19         }20         21         if(i==strs.length) return "0";22         return sb.toString().substring(i);23     }24     25     public class myComparator implements Comparator<String>{26         public int compare(String a, String b){27             String ab = a+b;28             String ba = b+a;29             return Integer.parseInt(ab)-Integer.parseInt(ba);30         }31     }32 }