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.

I was in the approach when I tried to sort the array. In fact, we do need to sort the array, but not in the traditional way.

If we look at the example, we will quickly figure out that we need to compare the most significant digit in the array, then probably the next, and so on. But the question is, how to do it in an acceptable time manner? Besides, why do we need to put 3 in front of 30?

Thinking the problem in another way: Randomly pick two numbers XYZ and ABC from the array, why do we want to put XYZ (ABC) in advance of ABC(XYC)? Because if we combine two numbers, XYZABC (ABCXYZ) will be larger than ABCXYZ (XYZABC). For example, 3 and 30, 330 is larger than 303, so we want to put 3 in front of 30.

So the only thing we need to do is to write a comparator to compare the concatenations of two numbers, and sort the entire array!

Easier than you thought, right?

Note on string.concat() and +
String.concat() will throw a NullPointerException if either of the string is null, but a + b will return, very interesting:

It treats b as b = "null". Another way to look at + can be like this: 

public static String plus(String a, String b) {
  StringBuilder sb = new StringBuilder();
  return sb.append(a).append(b).toString();
 }

The concat() method, from Java src is like this:

public String concat(String str) {
        int otherLen = str.length();
        if (otherLen == 0) {
            return this;
        }
        char buf[] = new char[count + otherLen];
        getChars(0, count, buf, 0);
        str.getChars(0, otherLen, buf, count);
        return new String(0, count + otherLen, buf);
    }

Update: 2015 - 03 - 01

Update comparator method, note the number may be very large and overflow. 

private class StringComparator implements Comparator{
        public int compare(String s1, String s2){
            return (int)(Long.parseLong(s1 + s2) - Long.parseLong(s2 + s1));
        }
    }

public String largestNumber(int[] num) {
        if (num == null || num.length == 0)
            return "";
        String[] s = new String[num.length];
        for (int i = 0; i < num.length; i++) {
            s[i] = String.valueOf(num[i]);
        }
        Arrays.sort(s, new StringComparator ());
        String rst = "";
        for (int i = s.length - 1; i >= 0; i--) {
            rst += s[i];
        }
        int i = 0;
        while (i < rst.length() && rst.charAt(i) == '0')
            i++;
        if (i == rst.length())
            return "0";
        return rst.substring(i);
        
    }
    private class StringComparator implements Comparator {
        public int compare (String a, String b) {
            return Integer.parseInt(a.concat(b)) - Integer.parseInt(b.concat(a));
        }
    }