Largest Number(lintcode 184)

Description

Given a list of non negative integers, arrange them such that they form the largest number.

Notice:
The result may be very large, so you need to return a string instead of an integer.

Example

Given [1, 20, 23, 4, 8], the largest formed number is 8423201.

Interface

public class Solution {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    public String largestNumber(int[] num) {
        // write your code here
    }
}

Solution

public class Solution {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    public String largestNumber(int[] num) {
        // write your code here
        String[] strs = new String[num.length];

        for (int i = 0; i < num.length; ++i) {
            strs[i] = Integer.toString(num[i]);
        }

        Arrays.sort(strs, new NumbersComparator());

        StringBuilder sb = new StringBuilder();

        for (String str : strs) {
            sb.append(str);
        }

        String result = sb.toString();

        if (result.charAt(0) == '0') {
            return "0";
        }

        return result;
    }

    private class NumbersComparator implements Comparator<String> {
        @Override
        public int compare(String a, String b) {
            return (b + a).compareTo(a + b);
        }
    }
}