Largest Number

Wed May 13 12:23:32 CST 2015 851 算法

文章摘要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.

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.

Credits:

Special thanks to @ts for adding this problem and creating all test cases.


Problem from: https://leetcode.com/

public class Solution {
    public String largestNumber(int[] num) {
       //将int数组转换为字符串数组
        String[] str = new String[num.length];
        for(int i = 0; i<num.length; i++){
            str[i] = num[i] + "";
        }

        /*按照下面描述的这种顺序进行排序
       *设有字符串a和b,若a和b按照不同的先后次序连接有ab和ba,
       *若ab>ba则a应该排在b前面,反之b应该在a前面
       */
        Arrays.sort(str, new MyComparator());
        
       //对已经排序好的字符串数组进行连接
        StringBuffer strBuffer = new StringBuffer("");
        for(int i = 0; i<str.length; i++){
            strBuffer.append(str[i]);
        }
        //若数组元素全为0,可能存在开头为0的情况,这时需要去掉
        String result = new String(strBuffer.toString());
        for(int i = 0; i<result.length(); i++){
            if(result.charAt(i) != '0') break;
            if(i == result.length()-1) result = "0";
        }
        
        return result;
    }
}

//比较器
class MyComparator implements Comparator<String>{
    @Override
    public int compare(String a, String b){
        String ab = a.concat(b);
        String ba = b.concat(a);
        long s=  Long.parseLong(ba) - Long.parseLong(ab);
        int result = (int)s;
        return result;
    }
}


打赏
打赏

分享到: