java把正整数数组排成一个最小的数

题目

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

思路

这道题是希望我们能找到一个排序规则，数组根据这个规则排序之后能排成一个最小的数字。利用贪心算法的贪心思想，要保证整个序列排成的数字最小，那么就要保证任意两个数字排序的相对数字最小。本质是需要我们考虑最小前缀和组合的问题。

在比较两个字符串 S1 和 S2 的大小时，应该比较的是 S1+S2 和 S2+S1 的大小，如果 S1+S2 < S2+S1，那么应该把 S1 排在前面，否则应该把 S2 排在前面。剑指Offer上作者给了严格的数学证明，证明了按拼接次序进行排序得到的数字串变成字符串后数字是最小的。

利用Java中的util工具包中的Arrays.sort()函数来实现对数组中的字符串两两排序的操作，我们只需要重写其中的Comparator比较器，使其按我们定义的规则对数组进行排序即可。附上相关API供读者参考：

Arrays.sort()方法的API（jdk1.8）

Comparator的compare方法的API（jdk1.8）

上代码

import java.util.ArrayList; import java.util.Arrays; import java.util.Comparator; public class Solution { public String PrintMinNumber(int [] numbers) { int len = numbers.length; if(len == 0){ return ""; } if(len == 1){ return String.valueOf(numbers[0]); } String [] array = new String[len]; for(int i = 0;i < len;i++ ){ array[i] = String.valueOf(numbers[i]); Arrays.sort(array,new Comparator<String>(){ public int compare(String s1,String s2){ String c1 = s1 + s2; String c2 = s2 + s1; return c1.compareTo(c2); } }); } StringBuffer retStr = new StringBuffer(); for(int i = 0;i < len;i++){ retStr.append(array[i]); } return retStr.toString(); } } 

本文地址：https://blog.csdn.net/weixin_45453028/article/details/107701986