179. Largest Number

   

• Total Accepted: 65743
• Total Submissions: 304090
• Difficulty: Medium
• Contributors: Admin

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  for adding this problem and creating all test cases.

【题目分析】

给定一个非负数的数组，返回由这个数组中的数组合构成的最大的数，由于所构成的数值可能很大，所以以字符串的形式返回。

【思路】

这实际上是一个对字符串排序的题目，如果我们把给定的数组按照某种方式排序，然后再把结果给组合起来，那么就可以得到我们想要的结果。那么如何排序呢？

给定两个字符串s1 = "30", s2 = "34"，我们尝试他们组成数值的组合"3034"和"3430"，"3430" > "3034". 因此"34" > "30".

再比如s1 = "9", s2 = "30"，我们尝试他们组成数值的组合"309"和"930"，"930" > "309". 因此"9" > "30".

【java代码】

代码中我们新建了一个构造器，通过这个构造器来对字符串数组进行排序，然后用stringbuilder把排序后的字符串组合到一起得到最后的结果。

1 public class Solution { 2     public String largestNumber(int[] nums) { 3         if(nums == null || nums.length == 0) return ""; 4          5         String[] s_nums = new String[nums.length]; 6          7         for(int i = 0; i < nums.length; i++) { 8             s_nums[i] = String.valueOf(nums[i]); 9         }10         11         Comparator
        
          comp = new Comparator
         
          () {12             public int compare(String str1, String str2) {13                 String s1 = str1 + str2;14                 String s2 = str2 + str1;15                 return s2.compareTo(s1);16             }17         };18         19         Arrays.sort(s_nums, comp);20         21         if(s_nums[0].charAt(0) == '0') return "0";22         23         StringBuilder sb = new StringBuilder();24         for(String s : s_nums) {25             sb.append(s);26         }27         28         return sb.toString();29     }30 }