首页 > 代码库 > Reorder array to construct the minimum number

Reorder array to construct the minimum number

Construct minimum number by reordering a given non-negative integer array. Arrange them such that they form the minimum number.

Notice

The result may be very large, so you need to return a string instead of an integer.

Have you met this question in a real interview?
 
 
Example

Given [3, 32, 321], there are 6 possible numbers can be constructed by reordering the array:

3+32+321=3323213+321+32=33213232+3+321=32332132+321+3=323213321+3+32=321332321+32+3=321323

So after reordering, the minimum number is 321323, and return it.

分析:

这里需要对数组进行排序,那么怎么比较大小呢?对于数A和B,如果AB在一起组成的数小于BA组成的数,我们就认为A<B,反之亦然。

 1 public static String minNumber(int[] nums) { 2     if (nums == null || nums.length == 0) 3         return ""; 4  5     String[] strs = new String[nums.length]; 6     for (int i = 0; i < nums.length; i++) { 7         strs[i] = String.valueOf(nums[i]); 8     } 9 10     Arrays.sort(strs, new Comparator<String>() {11         public int compare(String str1, String str2) {12             return (str1 + str2).compareTo(str2 + str1);13         }14     });15 16     StringBuilder sb = new StringBuilder();17     for (String str : strs) {18         sb.append(str);19     }20     for (int i = 0; i < sb.length(); i++) {21         if (sb.charAt(i) != 0) {22             return sb.substring(i);23         }24     }25     return "0";26 }

 

Reorder array to construct the minimum number