leetcode [#179] | GCidea's blog

JerryXia 发表于 2018-04-09 15:15:15 , 阅读 (6)

1. 题目
2. 解决方案
3. 注意事项

题目

Given a list of non negative integers, arrange them such that they form the largest number.
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.

解决方案

public class Solution {
    public String largestNumber(int[] nums) {
        //如果为空，直接返回空串
        if(nums == null || nums.length == 0)
            return "";
        
        //将数字数组转换为字符串数组，便于排序
        String[] s_num = new String[nums.length];
        for(int i = 0; i < nums.length; i++){
            s_num[i] = String.valueOf(nums[i]);
        }
            
        //实现Comparator接口用来定义排序规则
        Comparator<String> comp = new Comparator<String>(){
            @Override
            public int compare(String str1, String str2){
                String s1 = str1 + str2;
                String s2 = str2 + str1;
                return s2.compareTo(s1);
            }
       };
        
       //数组排序
       Arrays.sort(s_num, comp);
              
       //如果排序后数组第一个元素是0，则说明都是零，直接返回“0”即可         
       if(s_num[0].charAt(0) == '0'){
           return "0";
       }
        
       //否则，使用StringBuilder将字符串数组中每一项连起来即可
       StringBuilder sb = new StringBuilder();
       for(String s: s_num){
            sb.append(s);
       }
       
        return sb.toString();
    }
}

注意事项

1.曾考虑以下想法：

对于两个要比较的数，将长度补齐，并且较短的末尾是用0补齐
对于两个要比较的数，将长度补齐，并且较短的末尾是用个位数补齐

　这两种方法都需要考虑不少特殊情况再单独做出判断，不是很完整。

2.上述方法是借鉴discuss中vote较高的回答。核心是实现Comparator接口用来定义排序规则，用此规则使用Arrays.sort排序。

3.由于最后要做字符串拼接，因此务必使用StringBuilder而非String直接相连，大大提高性能。

[ 技术文章推荐 ]