解题思路
- 对每次输入的字符串样本,通过substr()得到后六位子串。
- 把每个子串通过stoi转换为整型,并把结果插入到容器mutiset中,自动完成排序。
- 最后遍历容器mutiset即可得到顺序排列的数据集。
完整代码
#include<iostream>
#include<string>
#include<set>
using namespace std;
int main()
{
int M=0;
cin>>M;
string s;// 获取每个字符串样本
multiset<int> ms;// ms用来存储后六位数字并排序
while(M--)
{
cin>>s;
// 1、先通过substr得到后六位纯数字的子串
// 2、再通过stoi把该子串转为整型并插入到ms中
ms.insert(stoi(s.substr(s.size()-6)));
}
// 最后遍历ms即可得到排序好的数据
for(auto& e : ms)
{
cout<<e<<endl;
}
return 0;
}
性能分析
- 时间复杂度:O(nlogn)。即容器内部排序的时间复杂度O(logn!) = O(nlogn)。
- 空间复杂度:O(n)。n组数据,创建了n个节点。