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.

Solution:

对于两个备选数字a和b，如果str(a) + str(b) > str(b) + str(a)，则a在b之前，否则b在a之前

按照此原则对原数组从大到小排序即可。 Collections.sort() guaranteed the nlogn performance, 所以时间复杂度O（nlogn）。

易错样例：

Input:     [0,0]

Output:    "00"

Expected:  "0"

public class Solution {
    public String largestNumber(int[] num) {
        if(num == null || num.length == 0)
            return null;
        
        ArrayList list = new ArrayList();
        for(int n : num) {
            list.add(n);
        }
        
        //define a comparator first to sort the integer
        Comparator comp = new Comparator() {
            @Override
            public int compare(Integer n1, Integer n2) {
                String s1 = "" + n1 + n2;
                String s2 = "" + n2 + n1;
                return s2.compareTo(s1);
                //condition1: if s1 < s2, 
                //s2.compareTo(s1) will return positive number which is opposite with original order,
                //so descending order.
                //condition2: if s1 > s2,
                //s2.compareTo(s1) will return negative number which is opposite with original order,
                //so still descending order.
                
            }
        };
        //Sorts the list according to the order induced by the comp.
        Collections.sort(list, comp);
        
        StringBuilder str = new StringBuilder();
        for(int n : list) {
            str.append(n);
        }
        
        //if string is 0000..., only return one 0
        if(str.charAt(0) == '0')
            return "0";
        
        return str.toString();
    }
}

=========================================================

Collections.sort()

public static <T> void sort(List<T> list,
                            Comparator<? super T> c)

Sorts the specified list according to the order induced by the specified comparator. All elements in the list must be mutually comparable using the specified comparator (that is,c.compare(e1, e2) must not throw a ClassCastException for any elements e1 and e2 in the list).This sort is guaranteed to be stable: equal elements will not be reordered as a result of the sort.
The sorting algorithm is a modified mergesort (in which the merge is omitted if the highest element in the low sublist is less than the lowest element in the high sublist). This algorithm offers guaranteed n log(n) performance. The specified list must be modifiable, but need not be resizable. This implementation dumps the specified list into an array, sorts the array, and iterates over the list resetting each element from the corresponding position in the array. This avoids the n² log(n) performance that would result from attempting to sort a linked list in place.

Parameters:

list - the list to be sorted.

c - the comparator to determine the order of the list. A null value indicates that the elements' natural ordering should be used.

CompareTo()
The method compareTo() is used for comparing two strings lexicographically. Each character of both the strings is converted into a Unicode value for comparison. 
If both the strings are equal then this method returns 0 else it returns positive or negative value. 
The result is positive if the first string is lexicographically greater than the second string else the result would be negative.