2015年6月6日星期六

[LeetCode] Largest Number

Problem:

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.

Java Code:


public class Solution {
    public String largestNumber(int[] num) {
                StringBuilder result = new StringBuilder();
        
        if (num == null) {
            return new String(result);
        }
        
        Integer[] sorted = new Integer[num.length];
        for (int i = 0; i < num.length; i++) {
            sorted[i] = new Integer(num[i]);
        }
        
        Arrays.sort(sorted, new Comparator<Integer>(){
            @Override
            public int compare(Integer a, Integer b){
                if (a == 0 || b == 0) {
                    return a == 0 ? 1 : -1;
                }
                String s1 = a.toString() + b.toString();
                String s2 = b.toString() + a.toString();
                int i = 0;
                while (i < s1.length()) {
                    if (s1.charAt(i) > s2.charAt(i)) {
                        return -1;
                    }
                    if (s1.charAt(i) < s2.charAt(i)) {
                        return 1;
                    }
                    i++;
                }
                return 1;
            }
        });
        
        boolean flag = true;
        for (int i = 0; i < sorted.length; i++) {
            if (sorted[i] != 0) {
                flag = false;
            }
            result.append(Integer.toString(sorted[i]));
        }
        
        if (flag) {
            return "0";
        }
        
        return new String(result);
    }
    
}

没有评论:

发表评论