题目：

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.

链接：

题解：

用数组中的数字组合出一个最大的数，返回String。直接的想法是对数组中的数字做一个排序，再用排序好的数字来输出结果。这里排序的过程需要用一个Comparator，比较简便的方法是我们把int[]换乘String[]，然后对String[]中的每个String进行逐字比较。

之前还想过求数字最高位数的方法，比如给定n,那么最高位c = n / Math.pow(10, log10(n))，但比较的话还得转成Integer，比较麻烦，不如用String Comparator方便。

Time Complexity - O(nlogn)， Space Complexity - O(n)

public class Solution {    public String largestNumber(int[] nums) {        if(nums == null || nums.length == 0)            return "";        String[] numsAsStrings = new String[nums.length];                    for(int i = 0; i < nums.length; i++)            numsAsStrings[i] = String.valueOf(nums[i]);                Arrays.sort(numsAsStrings, new Comparator
     
      () {           //anonymous new comparator            public int compare(String s1, String s2) {                String s1s2 = s1 + s2;                String s2s1 = s2 + s1;                return s2s1.compareTo(s1s2);            }        });                if(numsAsStrings[0].equals("0"))                    // for corner case "00"            return "0";                StringBuilder sb = new StringBuilder();                for(String str : numsAsStrings)            sb.append(str);                return sb.toString();    }}
     

 

二刷:

沿用了一刷的方法。但用Lambda就比较慢，可能还是Java编译器的问题。

Java:

public class Solution {    public String largestNumber(int[] nums) {        if (nums == null || nums.length == 0) return "";        int len = nums.length;        String[] strs = new String[len];        for (int i = 0; i < len; i++) strs[i] = String.valueOf(nums[i]);        Arrays.sort(strs, (String s1, String s2) -> (s2 + s1).compareTo(s1 + s2));        if (strs[0].charAt(0) == '0') return "0";        StringBuilder sb = new StringBuilder();        for (String str : strs) sb.append(str);        return sb.toString();    }}

 

测试：