java把正整数数组排成一个最小的数
程序员文章站
2022-03-10 10:37:25
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{3,32,321},则打印出这三个数字能排成的最小数字为321323。...
题目
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。例如输入数组{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
推荐阅读
-
[PHP] 算法-把数组排成最小的数的PHP实现
-
c语言和Java语言实现,两数之和:给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
-
将数组排成最小的数
-
【剑指 Offer 45】 把数组排成最小的数
-
Java求一个数组中的最大值和最小值
-
java把正整数数组排成一个最小的数
-
输入10个整数,将其中最小的数与第一个数对换,把最大的数与最后一个属兑换。写三个函数:1.输入10个数;2.进行处理;3.输出10个数
-
把数组排成最小的数
-
PHP把一个指定的数,随机的分配到指定书目的数组中
-
Java_冒泡排序|获取数组最大值和最小值操作,编写函数得到0到n之间的随机数,并找出产生m个这样的随机数中最大的、最小的数,并统计其中>=60的有多少个