原题(来源Leetcode)
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2] 输出: "102"
示例 2:
输入: [3,30,34,5,9] 输出: "3033459"
提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
解法
思想
将数组排序,类似于动态规划的思想,两个数之间相互连接比较一下。
代码
class Solution {
public String minNumber(int[] nums) {
String[] strings = new String[nums.length];
for(int i = 0;i<nums.length;i++){
strings[i] = String.valueOf(nums[i]);
}
Arrays.sort(strings,(s1,s2)->{
String link1 = s1+s2;
String link2 = s2+s1;
for(int i = 0;i<link1.length();i++){
if(link1.charAt(i)!=link2.charAt(i)) return link1.charAt(i)-link2.charAt(i);
}
return 0;
});
StringBuilder sb = new StringBuilder();
for(String i:strings){
sb.append(i);
}
return sb.toString();
}
}
原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/%e5%89%91%e6%8c%87offer45-%e6%8a%8a%e6%95%b0%e7%bb%84%e6%8e%92%e6%88%90%e6%9c%80%e5%b0%8f%e7%9a%84%e6%95%b0/