Question:

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.

Thinking:

I suppose we should sort the numbers in order. For example, if there are two nums, we convert them into strings. Then compare the connection of s1 + s2 and connection s2 + s1. Make sure the compare method. Then what we need is connecting them together.

Solution:

public String largestNumber(int[] nums) {
    PriorityQueue<String> maxHeap = new PriorityQueue<String>(new NumComparator());
    StringBuilder res = new StringBuilder();

    for (int num: nums)
        maxHeap.add(Integer.toString(num));

    while (!maxHeap.isEmpty())
        res.append(maxHeap.poll());

    return res.toString().charAt(0) == '0'? "0" : res.toString();
}

public class NumComparator implements Comparator<String> {

    @Override
    public int compare(String s1, String s2) {
        String str1 = s1 + s2;
        String str2 = s2 + s1;

        return str2.compareTo(str1);
    }
}