剑指 Offer 45. 把数组排成最小的数
中等
662
相关企业
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
这道题在左程云算法课上讲过,但是这次做却完全没有印象了,只能大概想到需要排序。
方法一:使用内置排序函数
重点是:比较器的定义,这里使用lambda函数。
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,(x,y)->(x+y).compareTo(y+x));
StringBuilder builder = new StringBuilder();
for(String s:strs){
builder.append(s);
}
return builder.toString();
}
}
方法二:自己写一个快速排序
一篇非常棒的快速排序算法博文
注意快速排序算法的分析要区分理想情况和最坏情况。文章来源:https://www.toymoban.com/news/detail-619425.html
时间复杂度 | 空间复杂度 | |
---|---|---|
理想情况 | O ( n l o g n ) O(nlogn) O(nlogn) | O ( l o g n ) O(logn) O(logn) |
最坏情况 | O ( n 2 ) O(n^2) O(n2) | O ( n ) O(n) O(n) |
注:文章来源地址https://www.toymoban.com/news/detail-619425.html
- 这里理想情况下的时间复杂度计算需要使用到Master公式(如果我没记错的话,应该是这名字,这个公式分析了递归函数内部调用子递归的次数等,推算出一个递归算法的时间复杂度。)
- 这里的空间复杂度是原地排序情况下的额外空间复杂度,主要是调用递归,使用了栈空间。
// 这里的代码参考了LeetCode评论区,谢谢大佬
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i=0;i<nums.length;i++){
strs[i] = Integer.toString(nums[i]);
}
quickSort(strs,0,strs.length-1);
StringBuilder builder = new StringBuilder();
for(String s:strs){
builder.append(s);
}
return builder.toString();
}
public void quickSort(String[] strs, int low, int high){
if(low<high){
int middle = partition(strs,low,high);
quickSort(strs,low,middle-1);
quickSort(strs,middle+1,high);
}
}
public int partition(String[] strs,int low, int high){
String temp = strs[low];// chosen as pivot
while(low<high){
// must put this group "high--" ahead of that group "low++",先去处理右端,拿到右端的小值后,赋值到左端,再处理左端
while(low<high && (strs[high]+temp).compareTo(temp+strs[high])>=0){// 注意这里是>=
high--;
}
strs[low] = strs[high]; // 此时strs[low]已经被记录下来了(可能记录在temp,也可能在之前的strs[high]),所以可以被覆盖
while(low<high && (strs[low]+temp).compareTo(temp+strs[low])<=0){
low++;
}
strs[high]=strs[low];
}
strs[low]=temp;// 此时low指针来到“等于区”“中间区”
return low;// 返回pivot的位置,此时strs中的当前段的左边都是“小于”pivot,右边都是“大于”pivot的
}
到了这里,关于剑指 Offer 45. !!把数组排成最小的数(使用比较器的定制排序;快速排序)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!