把数组排成最小的数
难度:中等
描述
输入一个非负整数数组numbers,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
例如输入数组[3,32,321],则打印出这三个数字能排成的最小数字为321323。
1.输出结果可能非常大,所以你需要返回一个字符串而不是整数
2.拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
数据范围
0<=len(numbers)<=100
举例
解题思路
本题最直观的解法就是求出数组中所有数字的全排列,然后比较所有的排列,最后找到最小的排列,但是时间复杂度为O(n!),所以不是一个好的解法。
换一种思路可以发现,本题实际上希望我们找到一个排序规则,数组根据这个排序规则进行重排之后可以连成一个最小的数字。要确定这样的排序规则,也就是对于两个数字m和n,通过一个规则确定哪个应排在前面。
根据题目要求,我们可以发现,两个数字m和n能拼接成mn和nm,如果mn
若mn>nm,则m大于n
若mn
若mn=nm,则m等于n
根据上述规则,我们需要先把数字转换成字符串再进行比较,因为需要拼接起来。比较完之后按顺序连接成一个字符串即可。
编程实现(java)
import java.util.*; public class Solution { public String PrintMinNumber(int [] numbers) { //空数组的情况 if(numbers == null || numbers.length == 0) return ""; String[] nums = new String[numbers.length]; //将数字转成字符 for(int i = 0; i < numbers.length; i++) nums[i] = numbers[i] + ""; //按照重载排序 Arrays.sort(nums, new Comparator() { public int compare(String s1, String s2) { return (s1 + s2).compareTo(s2 + s1); } }); StringBuilder res = new StringBuilder(); //字符串叠加 for(int i = 0; i < nums.length; i++) res.append(nums[i]); return res.toString(); } }