C++描述将 01 串首先按长度排序长度相同时按 1的个数多少进行排序1的个数相同时再按 ASCII 码值排序字典序。输入描述第一行输入一个整数 n 1≤n≤100表示字符串的个数。输入数据中含有一些 01 串01 串的长度不大于 256个字符。输出描述重新排列 01 串的顺序使得串按基本描述的方式排序然后依次输出。
思路:
- 定义一个结构体,包含一个字符串变量和两个int变量,分别表示长度和1的个数。
- 使用vector容器,将输入的所有字符串按照长度、1的个数和ASCII码值分别排序。
- 遍历排序后的vector容器,依次输出排序后的字符串。
C++代码实现:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct StringInfo {
string str;
int length;
int count;
};
bool comp(const StringInfo& a, const StringInfo& b) {
if (a.length != b.length) {
return a.length < b.length;
} else if (a.count != b.count) {
return a.count < b.count;
} else {
return a.str < b.str;
}
}
int main() {
int n;
cin >> n;
vector<StringInfo> strs;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
int length = s.length();
int count = 0;
for (int j = 0; j < length; j++) {
if (s[j] == '1') {
count++;
}
}
strs.push_back({s, length, count});
}
sort(strs.begin(), strs.end(), comp);
for (int i = 0; i < n; i++) {
cout << strs[i].str << endl;
}
return 0;
}
复杂度分析:
- 时间复杂度:排序的时间复杂度为O(nlogn),遍历输出的时间复杂度为O(n),总时间复杂度为O(nlogn)。
- 空间复杂度:使用了一个vector容器来存储输入的字符串,空间复杂度为O(n)
原文地址: http://www.cveoy.top/t/topic/irou 著作权归作者所有。请勿转载和采集!