Lintcode算法

2018/06/11 11:23
阅读数 0

题目:

给出一组非负整数,重新排列他们的顺序把他们组成一个最大的整数。

样例

给出 [1, 20, 23, 4, 8],返回组合最大的整数应为8423201

思路:直接交换两个数,然后判断交换之后的大小,并根据交换之后的结果,对数组进行排序,使其从数组的开始到数组的结束,组成的数字的最大。另外因为考虑到,可能会出现数据出现溢出的现象,需要先把整数的数组转化为字符串类型的数组。例如:对于2和23,谁应该排在前边,那么我们就对223和232进行字符串比大小,将组合成结果大的数字的23放在2的前面。

class Solution {
    /**
     * @param nums: A list of non negative integers
     * @return: A string
     */
    public String largestNumber(int[] nums) {
        // write your code here
    	String[] s=new String[nums.length];
    	for(int i=0;i<nums.length;++i){
    		s[i]=Integer.toString(i);
    	}
    	//对字符串数组进行排序
    	Arrays.sort(s,new Comparator<String>(){

			@Override
			public int compare(String o1, String o2) {
				//升序是前者减去后者,降序是后者减去前者。因为排序规则,就是结果就是将数组重新排序,能够从头到尾,实现最大值的问题,所以采用降序
				return (o2+o1).compareTo(o1+o2);
				
			}
    	});
    	StringBuffer buf=new StringBuffer();
    	for(String temp:s){
    		buf.append(temp);
    	}
    	int index=0;
    	String string = buf.toString();
    	while(index<string.length()&&string.charAt(index)=='0'){
    		index++;
    	}
    	if(string.length()==0) return "0";
    	return buf.substring(index);
       
    }
        
    
}

  

 

 

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部