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.

Analysis

1. 把int[] 转换为String[]
2. override String的compare方法
3. sort String[]
4. 把sort以后的string都append到一个string里return

注意：为什么不能直接用default的string sort？ 考虑case：如果有数“30”和“3”，default认为“30”>“3”，新定义的comparator认为“30”<“3”，为我们需要的情况。

Code

public class Solution {
    public String largestNumber(int[] nums) {
        if(nums==null || nums.length==0) {return "";}
        String[] str = new String[nums.length];
        for(int i=0; i<nums.length; i++){
            str[i]=nums[i]+"";
        }

        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                String s1 = str1+str2;
                String s2 = str2+str1;
                return s1.compareTo(s2);
            }
        };

        Arrays.sort(str, comp);

        if (str[str.length-1].charAt(0)=="0"){return "0";}
        StringBuilder sb = new StringBuilder();
        for(int i=str.length-1; i>=0; i--){
            sb.append(str[i]);
        }
        return sb.toString();
    }
}

Note

• String1.compareTo(String2) tutorial
• 如果相等，返回0，如果string1大，返回>0，如果string2大，返回<0

Reference

Leetcode