剑指 Offer 45. 把数组排成最小的数
题目
剑指 Offer 45. 把数组排成最小的数 难度：medium
输入一个非负整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: "102"示例 2:
输入: [3,30,34,5,9]
输出: "3033459"提示:
0 < nums.length <= 100
方法一：排序
思路
此题求拼接起来的最小数字，本质上是一个排序问题。设数组 numsnums 中任意两数字的字符串为 xx 和 yy ，则规定 排序判断规则 为：
- 若拼接字符串 $x + y > y + x$ ，则 $x > y$；
- 反之，若 $x + y < y + x$ ，则 $x < y$；
根据以上规则，套用任何排序方法对 $nums$ 执行排序即可。
- 初始化： 字符串列表 $strs$ ，保存各数字的字符串格式；
- 列表排序： 应用以上 “排序判断规则” ，对 $strs$ 执行排序；
- 返回值： 拼接 $strs$ 中的所有字符串，并返回。
解题
Python：
class Solution:
def minNumber(self, nums: List[int]) -> str:
def quick_sort(l , r):
if l >= r: return
i, j = l, r
while i < j:
while strs[j] + strs[l] >= strs[l] + strs[j] and i < j: j -= 1
while strs[i] + strs[l] <= strs[l] + strs[i] and i < j: i += 1
strs[i], strs[j] = strs[j], strs[i]
strs[i], strs[l] = strs[l], strs[i]
quick_sort(l, i - 1)
quick_sort(i + 1, r)
strs = [str(num) for num in nums]
quick_sort(0, len(strs) - 1)
return ''.join(strs)Java：
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]);
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);
}
}
题目名字
题目
剑指 Offer 61. 扑克牌中的顺子 难度：easy
从若干副扑克牌中随机抽 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
方法一：排序
思路
根据题意，此 5 张牌是顺子的 充分条件 如下：
- 除大小王外，所有牌 无重复 ；
- 设此 5 张牌中最大的牌为 $max$，最小的牌为 $min$（大小王除外），则需满足：
$$ max−min<5 $$
因而，可将问题转化为：此 55 张牌是否满足以上两个条件？
- 先对数组执行排序。
- 判别重复： 排序数组中的相同元素位置相邻，因此可通过遍历数组，判断 $nums[i] = nums[i + 1]$ 是否成立来判重。
- 获取最大 / 最小的牌： 排序后，数组末位元素 $nums[4]$ 为最大牌；元素 $nums[joker]$ 为最小牌，其中 $joker$ 为大小王的数量。
解题
Python：
class Solution:
def isStraight(self, nums: List[int]) -> bool:
joker = 0
nums.sort() # 数组排序
for i in range(4):
if nums[i] == 0: joker += 1 # 统计大小王数量
elif nums[i] == nums[i + 1]: return False # 若有重复，提前返回 false
return nums[4] - nums[joker] < 5 # 最大牌 - 最小牌 < 5 则可构成顺子Java：
class Solution {
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 则可构成顺子
}
}
后记
📝 上篇精讲： 【算法题解】 Day30 搜索与回溯
💖 我是 𝓼𝓲𝓭𝓲𝓸𝓽，期待你的关注；
👍 创作不易，请多多支持；
🔥 系列专栏： 算法题解
