Largest Number

Source

• lintcode: Largest Number

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

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

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

Challenge
Do it in O(nlogn) time complexity.

Java

public class Solution {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    public String largestNumber(int[] nums) {
        if(nums==null || nums.length==0) return "";
        String[] Snum = new String[nums.length];
        for(int i=0; i<nums.length; i++){
            Snum[i]=Integer.toString(nums[i]);
        }

        Comparator<String> cmp = new Comparator<String>(){
            public int compare(String str1, String str2){
                String s1 = str1+str2;
                String s2 = str2+str1;
                return s2.compareTo(s1);
            }
        };
        Arrays.sort(Snum, cmp);
        if(Snum[0].equals("0")){
            return "0";    
        }
        StringBuilder sb = new StringBuilder();
        for(String s: Snum){
            sb.append(s);
        }
        return sb.toString();
    }
}