❓ 剑指 Offer 45. 把数组排成最小的数
难度:中等
输入一个非负整数数组,把数组里所有数字拼接起来排成一个数,打印能拼接出的所有数字中最小的一个。
示例 1:
输入: [10,2]
输出: “102”
示例 2:
输入: [3,30,34,5,9]
输出: “3033459”
提示:
0 < nums.length <= 100
说明:
- 输出结果可能非常大,所以你需要返回一个字符串而不是整数
- 拼接起来的数字可能会有前导
0
,最后结果不需要去掉前导 0
💡思路:
可以看成是一个排序问题,在比较两个字符串
s1
和s2
的大小时,应该比较的是s1+s2
和s2+s1
的大小:
- 如果
s1+s2 < s2+s1
,那么应该把s1
排在前面,否则应该把s2
排在前面。
总体流程:
-
初始化: 字符串列表
strs
,保存各数字的字符串格式; -
列表排序: 应用以上 “排序判断规则” ,对
strs
执行排序; -
返回结果: 拼接
strs
中的所有字符串,并返回。
法一:快速排序
需修改快速排序函数中的排序判断规则。字符串大小(字典序)对比的实现方法:
- C++ 中可直接用
<
,>
; - Java 中使用函数
A.compareTo(B)
;
法二:内置函数
- C++ 定义为
(string& x, string& y){ return x + y < y + x; } ;
- Java 定义为
(x, y) -> (x + y).compareTo(y + x);
🍁代码:(C++、Java)
法一:快速排序
C++
class Solution {
private:
void quickSort(vector<string>& strs, int l, int r){
if(l >= r) return;
int i = l + 1, j = r;
while(i <= j){
//从前往后找第一个比str[l] 大的字符串
while(i <= j && strs[i] + strs[l] <= strs[l] + strs[i])i++;
//从后往前找第一个比str[l] 小的字符串
while(i <= j && strs[j] + strs[l] >= strs[l] + strs[j])j--;
//交换
if(i < j)
swap(strs[i++], strs[j--]);
}
swap(strs[l], strs[j]);
quickSort(strs, l, j - 1);
quickSort(strs, j + 1, r);
}
public:
string minNumber(vector<int>& nums) {
// 1. 初始化
vector<string> strs;
for(int i = 0; i < nums.size(); i++){
strs.push_back(to_string(nums[i]));
}
// 2. 排序
quickSort(strs, 0, strs.size() - 1);
// 3. 返回结果
string ans;
for(string s : strs){
ans.append(s);
}
return ans;
}
};
Java
class Solution {
private void quickSort(String[] strs, int l, int r){
if(l >= r) return;
int i = l + 1, j = r;
String temp;
while(i <= j){
//从前往后找第一个比str[l] 大的字符串
while(i <= j && (strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0)i++;
//从后往前找第一个比str[l] 小的字符串
while(i <= j && (strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0)j--;
//交换
if(i < j){
temp = strs[i];
strs[i++] = strs[j];
strs[j--] = temp;
}
}
//此时j + 1 = i,strs[i]左边的字符串一定比strs[l]小,strs[j]右边的字符串一定比strs[l]大
temp = strs[l];
strs[l] = strs[j];
strs[j] = temp;
quickSort(strs, l, j - 1);
quickSort(strs, j + 1, r);
}
public String minNumber(int[] nums) {
// 1. 初始化
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++){
strs[i] = String.valueOf(nums[i]);
}
// 2. 排序
quickSort(strs, 0, strs.length - 1);
// 3. 返回结果
StringBuilder ans = new StringBuilder();
for(String s : strs){
ans.append(s);
}
return ans.toString();
}
}
法二:内置函数
C++
class Solution {
public:
string minNumber(vector<int>& nums) {
// 1. 初始化
vector<string> strs;
for(int i = 0; i < nums.size(); i++){
strs.push_back(to_string(nums[i]));
}
// 2. 内置函数排序
sort(strs.begin(), strs.end(), [](string& x, string& y){return x + y < y + x;});
// 3. 返回结果
string ans;
for(string s : strs){
ans.append(s);
}
return ans;
}
};
Java
class Solution {
public String minNumber(int[] nums) {
// 1. 初始化
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++){
strs[i] = String.valueOf(nums[i]);
}
// 2. 内置函数排序
Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
// 3. 返回结果
StringBuilder ans = new StringBuilder();
for(String s : strs){
ans.append(s);
}
return ans.toString();
}
}
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
O
(
n
l
o
g
n
)
O(nlogn)
O(nlogn),其中
n
为数组的长度,使用快排或内置函数的平均时间复杂度为 O ( n l o g n ) O(nlogn) O(nlogn) ,最差为 O ( n 2 ) O(n^2) O(n2)。 -
空间复杂度:
O
(
n
)
O(n)
O(n),字符串列表
strs
占用线性大小的额外空间。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-694575.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-694575.html
注: 如有不足,欢迎指正!
到了这里,关于(排序) 剑指 Offer 45. 把数组排成最小的数 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!