leetcode179. 最大数

给定一组非负整数，重新排列它们的顺序使之组成一个最大的整数。

示例 1:

输入: [10,2]
输出: 210
示例 2:

输入: [3,30,34,5,9]
输出: 9534330
说明: 输出结果可能非常大，所以你需要返回一个字符串而不是整数。

思路：贪心，对于两个字符串，如果a+b<b+a，则交换位置。整体按这个标准排序即可。

有时候现场一时证明不了想的贪心策略是否正确，这时可以先尝试一下到底对不对，万一对了就赚了。

证明：

  

   

    

     

    
    

     

      class Solution {
     
    
   

    

     

    
    

     
 private class LargerNumberComparator implements Comparator<String> {
     
    
   

    

     

    
    

     
 @Override
     
    
   

    

     

    
    

     
 public int compare(String a, String b) {
     
    
   

    

     

    
    

     

       String order1 = a + b;
     
    
   

    

     

    
    

     

       String order2 = b + a;
     
    
   

    

     

    
    

     
 return order2.compareTo(order1);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 public String largestNumber(int[] nums) {
     
    
   

    

     

    
    

     

       String[] asStrs = new String[nums.length];
     
    
   

    

     

    
    

     
 for (int i = 0; i < nums.length; i++) {
     
    
   

    

     

    
    

     

       asStrs[i] = String.valueOf(nums[i]);
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       Arrays.sort(asStrs, new LargerNumberComparator());
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 if (asStrs[0].equals("0")) {
     
    
   

    

     

    
    

     
 return "0";
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

       String str = new String();
     
    
   

    

     

    
    

     
 for (String numAsStr : asStrs) {
     
    
   

    

     

    
    

     

       str += numAsStr;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     
 return str;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: fantianzuo.blog.csdn.net，作者：兔老大RabbitMQ，版权归原作者所有，如需转载，请联系作者。

原文链接：fantianzuo.blog.csdn.net/article/details/104292930