Leetcode: Largest Number

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 }