LeetCode 面试题45. 把数组排成最小的数
2020-05-06 16:14:30来源:博客园 阅读 ()
LeetCode 面试题45. 把数组排成最小的数
我的LeetCode:https://leetcode-cn.com/u/ituring/
我的LeetCode刷题源码[GitHub]:https://github.com/izhoujie/Algorithmcii
LeetCode 面试题45. 把数组排成最小的数
题目
输入一个正整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"
示例?2:
输入: [3,30,34,5,9]
输出: "3033459"
提示:
- 0 < nums.length <= 100
说明:
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/ba-shu-zu-pai-cheng-zui-xiao-de-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
解题思路
要想最终拼接值最小,需要尽可能把较小的数拼接在前面;
只要能保证两个数拼接后最小那么最终拼接的数就是最小的,所以问题可以转化为对nums的排序,排序的逻辑是两个数拼接后获得较小值时拼接在前的那个数“较小”;
比较的实现方式:
- 两个字符串的拼接比较,字符串的拼接比较结果与值的比较一致;
- 直接自定义实现两个数的比较逻辑;
思路1-转为字符串拼接比较
步骤:
- 把nums转为String类型的list,然后利用Collections.sort对list进行排序,需要实现Comparator的比较逻辑为字符串的拼接比较;
- 将排序后的list拼接返回;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(nlogn\right)}} $ 快排的耗时
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ list需要的空间
思路2-自定义int的比较逻辑
步骤:
- 对nums进行快排,比较的逻辑为自定义实现;
- 对于两个数num1和num2,各自的最高位权分别为base1和base2,那么比较的逻辑为:\(num1*base2+num2<num2*base1+num1\);
- 例子,对于45和336,最高位权分别为100和1000,比较的逻辑为:\(45*1000+336<336*100+45\);
- 将排序后的nums用StringBuilder拼接返回;
算法复杂度:
- 时间复杂度: $ {\color{Magenta}{\Omicron\left(nlogn\right)}} $ 快排耗时
- 空间复杂度: $ {\color{Magenta}{\Omicron\left(n\right)}} $ StringBuilder需要的空间
算法源码示例
package leetcode;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;
/**
* @author ZhouJie
* @date 2020年5月5日 下午9:15:03
* @Description: 面试题45. 把数组排成最小的数
*
*/
public class LeetCode_Offer_45 {
}
class Solution_Offer_45 {
/**
* @author: ZhouJie
* @date: 2020年5月5日 下午9:19:34
* @param: @param nums
* @param: @return
* @return: String
* @Description: 1-转为String,然后排序,比较逻辑为:拼接后的字符串小的排在最前面(字符小对应的数值也小);
*
*/
public String minNumber_1(int[] nums) {
List<String> list = new ArrayList<String>();
for (int val : nums) {
list.add(String.valueOf(val));
}
// 转为String后对每两个字符串拼接后比较排序;
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
// 字符拼接后的比较结果与值的拼接比较结果一致
return (o1 + o2).compareTo(o2 + o1);
}
});
return String.join("", list);
}
/**
* @author: ZhouJie
* @date: 2020年5月5日 下午9:28:53
* @param: @param nums
* @param: @return
* @return: String
* @Description: 2-重写int的sort排序,然后StringBuilder拼接;
*
*/
public String minNumber_2(int[] nums) {
quickSort(nums, 0, nums.length - 1);
StringBuilder sb = new StringBuilder();
for (int val : nums) {
sb.append(val);
}
return sb.toString();
}
/**
* @author: ZhouJie
* @date: 2020年5月5日 下午11:50:33
* @param: @param nums
* @param: @param start
* @param: @param end
* @return: void
* @Description: 快速排序
*
*/
private void quickSort(int[] nums, int start, int end) {
if (start >= end) {
return;
}
int i = start, j = end, mid = nums[start];
while (i < j) {
while (i < j && compare(nums[j], mid)) {
j--;
}
while (i < j && compare(mid, nums[i])) {
i++;
}
if (i < j) {
nums[i] = nums[i] ^ nums[j];
nums[j] = nums[i] ^ nums[j];
nums[i] = nums[i] ^ nums[j];
}
}
nums[start] = nums[i];
nums[i] = mid;
quickSort(nums, start, i - 1);
quickSort(nums, i + 1, end);
}
/**
* @author: ZhouJie
* @date: 2020年5月5日 下午11:50:46
* @param: @param num1
* @param: @param num2
* @param: @return
* @return: boolean
* @Description: 自定义int的拼接比较
*
*/
private boolean compare(int num1, int num2) {
long base1 = 10, base2 = 10;
while (num1 / base1 > 0) {
base1 *= 10;
}
while (num2 / base2 > 0) {
base2 *= 10;
}
return (num1 * base2 + num2) >= (num2 * base1 + num1);
}
}
原文链接:https://www.cnblogs.com/izhoujie/p/12835788.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- JVM常见面试题解析 2020-06-11
- 送你一份年薪百万的抖音Java岗内部面试题 2020-06-09
- 总结一些 Java 相关笔试、面试题,万一用上了呢 (=_=) -- 基 2020-06-08
- 最强Dubbo面试题,附带超级详细答案 2020-06-06
- 2020Java面试题及答案,命中率高达90% 2020-06-05
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash