AcWing 3610. 找位置
原题链接
简单
作者:
小小小陈
,
2022-02-25 17:07:34
,
所有人可见
,
阅读 176
字符串+Hash
笔记
- 有多个重复元素往往采用hash数组统计
- 输出结果与顺序有关最好从小到大遍历
- 跳过重复元素可以设置vis数组
- 输出要求太复杂了,注意特判处理
时间复杂度:
最坏:O(n^2)
最好:O(n)
代码
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
using namespace std;
const int N = 128; //ascii最多有128个字符
vector<int> h[N]; //哈希数组,记录重复字符出现的下标集合
bool vis[N]; //记录是否已输出
int t[N]; //统计出现的次数
int main() {
string str;
while(cin>>str) {
memset(h, 0, sizeof h); //清除上次记录
memset(vis, false, sizeof vis);
int n = str.length();
for(int i = 0; i < n; i++) h[str[i]].push_back(i); //记录重复字符及其下标集合
for(int i = 0; i < n; i++) { //遍历字符串
if(!vis[str[i]] && h[str[i]].size() > 1) { //若该字符之前未处理且为重复字符
for(int j = 0; j < h[str[i]].size(); j++) { //输出hash数组
if(j == 0) cout<<str[i]<<":"<<h[str[i]][j];
else cout<<","<<str[i]<<":"<<h[str[i]][j];
}
cout<<endl;
vis[str[i]] = true; //该重复字符已处理完毕
}
}
}
return 0;
}