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.

思路

Sort string array，comparator比较A + B和B + A，哪个大哪个优先级高。然后把sorted string array concat一下就可以。
注意如果input全是0，那么需要返回只有一个0。

Solution

Time: O(nlogn)
Space: O(n)

public class Solution {
    // DO NOT MODIFY THE LIST. IT IS READ ONLY
    public String largestNumber(final List<Integer> A) {
        List<String> strs = new ArrayList<>();
        for (int i = 0; i < A.size(); i ++) {
            int n = A.get(i);
            strs.add(String.valueOf(n));
        }
        Collections.sort(strs, new Comparator<String>() {
            @Override
            public int compare(String one, String two) {
                return (two + one).compareTo(one + two);
            }
        });
        StringBuilder sb = new StringBuilder();
        boolean nonZero = false;
        for (int i = 0; i < strs.size(); i ++) {
            if (nonZero || !strs.get(i).equals("0") || i == strs.size() - 1) { 
                sb.append(strs.get(i));
                nonZero = true;
            }
        }
        return sb.toString();
    }
}