179. 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.

链接：http://leetcode.com/problems/largest-number/

题解：

用数组中的数字组合出一个最大的数，返回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<String>() {           //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();
    }
}

测试：

179. Largest Number

相关推荐