剑指 Offer 45. 把数组排成最小的数
题目:输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
提示:
0 < nums.length <= 100
说明:
1、输出结果可能非常大,所以你需要返回一个字符串而不是整数
2、拼接起来的数字可能会有前导 0,最后结果不需要去掉前导 0
解题思路:
此题求拼接起来的最小数字,本质上是一个排序问题。设数组nums中任意两数字的字符串为x和y ,则规定排序判断规则为:
-
若拼接字符串x+y>y+x ,则x “大于” y ;
-
反之,若x+y<y+x ,则x “小于” y ;
x “小于” y 代表:排序完成后,数组中x应在y左边;“大于” 则反之。
根据以上规则,套用任何排序方法对nums执行排序即可。
算法流程:
- 初始化: 字符串列表strs ,保存各数字的字符串格式;
- 列表排序: 应用以上 “排序判断规则” ,对strs执行排序;
- 返回值: 拼接strs中的所有字符串,并返回。
复杂度分析:
- 时间复杂度O(NlogN) : N为最终返回值的字符数量(strs列表的长度≤N );使用快排或内置函数的平均时间复杂度为O(NlogN) ,最差为 O(N^2) 。
- 空间复杂度O(N) : 字符串列表strs占用线性大小的额外空间。
代码:
在此列举 快速排序 和 内置函数 两种排序方法,其他排序方法也可实现。
快速排序:
需修改快速排序函数中的排序判断规则。字符串大小(字典序)对比的实现方法:Java 中使用函数 A.compareTo(B);
class Method1{
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]);
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
void quickSort(String[] strs, int l, int r) {
if(l >= r) return;
int i = l, j = r;
String tmp = strs[i];
while(i < j) {
while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
strs[i] = strs[l];
strs[l] = tmp;
quickSort(strs, l, i - 1);
quickSort(strs, i + 1, r);
}
}
内置函数:
需定义排序规则:Java定义为 (x, y) -> (x + y).compareTo(y + x) ;
class Method2{
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 res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
剑指 Offer 61. 扑克牌中的顺子
题目:从扑克牌中随机抽5张牌,判断是不是一个顺子,即这5张牌是不是连续的。2~10为数字本身,A为1,J为11,Q为12,K为13,而大、小王为 0 ,可以看成任意数字。A 不能视为 14。
示例 1:
输入: [1,2,3,4,5]
输出: True
示例 2:
输入: [0,0,1,2,5]
输出: True
限制:
1、数组长度为 5
2、数组的数取值为 [0, 13].
解题思路:
根据题意,此5张牌是顺子的 充分条件 如下:
除大小王外,所有牌 无重复 ;
设此5张牌中最大的牌为max ,最小的牌为min(大小王除外),则需满足:max−min<5
因而,可将问题转化为:此5张牌是否满足以上两个条件?
方法一: 集合 Set + 遍历遍历五张牌,遇到大小王(即0)直接跳过。
- 判别重复: 利用 Set 实现遍历判重, Set 的查找方法的时间复杂度为O(1) ;
- 获取最大 / 最小的牌: 借助辅助变量ma和mi ,遍历统计即可。
复杂度分析:
- 时间复杂度O(N)=O(5)=O(1) : 其中N为nums长度,本题中N≡5 ;遍历数组使用O(N) 时间。
- 空间复杂度O(N)=O(5)=O(1) : 用于判重的辅助 Set 使用O(N) 额外空间。
代码:
class Method1{
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复,提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
方法二:排序 + 遍历
先对数组执行排序。
- 判别重复: 排序数组中的相同元素位置相邻,因此可通过遍历数组,判断nums[i]=nums[i+1] 是否成立来判重。
- 获取最大 / 最小的牌: 排序后,数组末位元素nums[4] 为最大牌;元素nums[joker]为最小牌,其中joker 为大小王的数量。
复杂度分析:
- 时间复杂度O(NlogN)=O(5log5)=O(1) : 其中N为nums长度,本题中N≡5 ;数组排序使用O(NlogN) 时间。
- 空间复杂度O(1) : 变量joker使用O(1)大小的额外空间。
代码:
class Method2{
public boolean isStraight(int[] nums) {
int joker = 0;
Arrays.sort(nums); // 数组排序
for(int i = 0; i < 4; i++) {
if(nums[i] == 0) joker++; // 统计大小王数量
else if(nums[i] == nums[i + 1]) return false; // 若有重复,提前返回 false
}
return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
总结:
又是一天过去了,学习需要不停的坚持!其实我们的生活当中处处都是知识!用罗曼·罗兰的话来说就是:“生活中不是缺少美,而是缺少发现美的眼睛”。用物理中的熵增定律来说:“我们其实一直在和熵值在做斗争”!用古话来说就是:“处处留心皆学问,人情练达即文章”!放弃很简单!但是坚持下来是特别难的!但是如果坚持下来了!那定将会有收获的!
世界上最煎熬的事情莫过于:等待和羁绊,为什么呢?因为都会耗费大量的时间去做,但又不得不做的事,然后感觉还没有收获!不知道小伙伴们是否也有同样的感觉呢?就好比:等的时候总觉得时间在悄悄地溜走,然后想做别的事情又无法去做,等到想做的时候却又没有当时的那种感觉了。再过一段时间又会后悔当时为什么没有去做!可能这就是想和做的本质区别吧!也是将来时和现在时的区别吧!过去已经过去,已经无法挽回!只能立足于现在来规划未来,然后一步一步的去落实!剩余的就靠自己去领悟了!
最后,愿我们都能在各行各业中能够取得不同的成就,不负亲人、朋友、老师、长辈和国家的期望!能够用自身的所学知识为国家贡献出自己的一份力量!一起加油!
2021年5月10日夜