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.

给定一个数组，里面存放的都是非负整数，要求我们用里面的元素组成一个最大的数。这里我们首先将数组转换成一个一个字符串数组，这样我们就可以自定义Arrays.sort方法了，我们用到了Comparator接口，通过重写compare方法，来得到一个最大的数。关键就是compare的实现，我们知道compare有两个参数p1, p2, 如果p1 < p2时返回-1， p1 = p2返回0，p1 > p2返回1。在这道题目中，我们将两个参数先相加s1 = p1 + p2, s2 = p2 + p1，这样得到两个新的参数。为了更清楚的解释，我们假设此时p1 = "34", p2 = "56", 所以s1 = "3456" , s2 = "5634"。按照题目的要求我们要得到一个最大的数，这时我们希望p2和p1交换位置，因为s2 > s1, 所以我们应该返回1，因此我们在compare中返回s2.compareTo(s1)即可。代码如下：

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