「这是我参与11月更文挑战的第17天,活动详情查看:2021最后一次更文挑战」
描述
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
- 示例 1:
输入: [10,2]
输出: "102"
复制代码
- 示例 2:
输入: [3,30,34,5,9]
输出: "3033459"
复制代码
- 提示
0 < nums.length <= 100
复制代码
解析
根据题意,这一题最关键的部分就是自定义排序,一旦找到排序的奇点,就可以轻而易举解决这一题。 我们判断两个数字谁大谁小的依据是,str1+str2是否大于str2+str1,其实就是这么简单。
示例
class Solution {
public String minNumber(int[] nums) {
//第一种方法,全排列,但是比较麻烦
//第二种方法就是按照一定顺序排列,也就是要重写比较器
//从首位到末尾开始比较
//所以手写一个冒泡,排好序以后用
//用新的比较器写一个冒泡排序
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++) {
strs[i] = String.valueOf(nums[i]);
}
Arrays.sort(strs, (o1, o2) -> (o1+o2).compareTo(o2+o1));
StringBuilder sb = new StringBuilder();
for (String x:strs) {
sb.append(x);
}
return sb.toString();
}
}
复制代码
运行结果:
执行结果:通过
执行用时:4 ms, 在所有 Java 提交中击败了97.52%的用户
内存消耗:38 MB, 在所有 Java 提交中击败了45.05%的用户
- 其他解法
下面这种方式是通过随机快排,切记排序不是简单对a,b排序,如排序12,543,那么应该比较的是12543 和 54312 这个直接找到每个数是多少位,然后相加即可 12000 + 54 与 54300 + 12 比较
class Solution {
public String minNumber(int[] nums) {
return minNumber4(nums);
}
public String minNumber4(int[] nums){
quickSortRandom(nums,0,nums.length-1);
StringBuilder sb = new StringBuilder(nums.length);
for(int i : nums) sb.append(i);
return sb.toString();
}
public void quickSortRandom(int[] A,int low,int high){
if(low < 0 || high >= A.length || low >= high ) return;
int q = partition(A,low,high);
quickSortRandom(A,low,q-1);
quickSortRandom(A,q+1,high);
}
public int partition(int[] A,int low,int high){
int rand = low + (int)(Math.random()*(high - low));
swap(A,rand,high);
int x = A[high],i = low - 1;
long a,b;
for(int j = low; j < high; j++){
a = 10;b = 10;
while(A[j] >= a) a *= 10;
while(x >= b) b *= 10;
if(A[j] * b + x <= A[j] + x * a){
i++;
swap(A,i,j);
}
}
swap(A,i+1,high);
return i + 1;
}
public void swap(int[] A,int i,int j){
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
}
复制代码
近期评论