Largest Number 184

Question

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.

Challenge

Do it in O(nlogn) time complexity.

Solution

这道题很简单，只要利用排序把高位大的数排到前面即可。把int数转换成string，然后利用string的compareTo方法，比较s1+s2和s2+s1即可。最后只要注意把前置的0去掉。

代码如下：

public class Solution {
    /**
     *@param num: A list of non negative integers
     *@return: A string
     */
    class myComparator implements Comparator<Integer>{
        public int compare(Integer a, Integer b){
                String s1 = a.toString();
                String s2 = b.toString();
                return (s2 + s1).compareTo(s1 + s2);
            }
    }

    public String largestNumber(int[] num) {
        // write your code here
        String res = "";
        if(num == null || num.length == 0){
            return res;
        }

        PriorityQueue<Integer> queue = new PriorityQueue<Integer>(1, new myComparator());

        for(int i = 0; i < num.length; i++){
            queue.add(num[i]);
        }

        while(!queue.isEmpty()){
            int curt = queue.poll();
            if(res.length() == 0 && curt == 0 && !queue.isEmpty()){
                continue;
            }
            res = res + curt;
        }
        return res;
    }
}