ABC432B 最小排列题解
大约 2 分钟排序
ABC432B 最小排列题解
【算法标签】 排序
【语法标签】 :string、sort、for循环、cin/cout
给定一个正整数 X,将 X 的各位数字重新排列(不允许前导零),使得得到的数尽可能小。
例如, 时,各位数字为 ,可以组成 309、390、903、930。其中不允许 039 和 093(有前导零)。最小值为 309。
输入描述:输入一个正整数 X。
输出描述:输出一个整数,表示将 X 的各位数字重新排列后能得到的最小的数(不允许前导零)。
数据范围:
- X 是正整数
解题思路
要得到各位数字重排后的最小数,且不能有前导零,核心步骤如下:
- 数字排序:将所有数字按从小到大排序,得到一个升序的字符序列。
- 处理前导零:排序后第一个非零数字与序列的第一个位置交换,保证最高位不为零,同时让高位尽可能小。
参考代码
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int main() {
string s;
cin >> s;
sort(s.begin(), s.end());
for (int i = 0; i < s.size(); ++i) {
if (s[i] != '0') {
swap(s[0], s[i]);
break;
}
}
cout << s << endl;
return 0;
}算法复杂度
- 时间复杂度:,其中 n 是数字的位数,排序的时间开销为主要部分。
- 空间复杂度:,存储字符串 s 所需的空间。
样例验证
输入:
390执行过程:
- 输入字符串
s = "390"。 - 排序后得到
s = "039"。 - 找到第一个非零字符
'3'(索引为 1),与索引 0 的字符'0'交换,得到s = "309"。 - 输出结果
309,与样例输出一致。
总结
本题的关键是利用排序快速生成升序排列的数字,再通过一次交换解决前导零问题,既保证了数字最小,又符合题目要求。
