⾯试题之在字符串中查出第⼀个只出现⼀次的字符的位置
样例：⽐如“abcdabc”，第⼀个只出现⼀次的字符为d，位置为3
解决⽅案1：O（n*n)的复杂度
遍历字符串中的每个字符，然后⽤该字符在字符串中进⾏查，如果没有到和当前字符相同的字符。则当前字符为第⼀个 只出现⼀次的字符。
解决⽅案2：O(n)的复杂度
采取空间换时间的策略
正则匹配到第一个关键字就停止开⼀个辅助数组，做哈希映射
第⼀次扫描时，更新在辅助数组中当前字符出现的次数。
hash查的时间复杂度为o(1)。
第⼆次扫描时，在辅助数组中通过查辅助数组看当前字符是否只出现了⼀次，从头到尾的顺序遍历保证了“第⼀个”，辅助数组的查保证了“只出现⼀次”。
code：
#include <bits/stdc++.h>
using namespace std;
int main()
{
string str="abcdabc";
//在字符串中查出第⼀个只出现⼀次的字符
//o(n) 空间换时间
int a[300];
memset(a,0,sizeof(a));
//第⼀次遍历统计各字符出现次数
for(int i=0;i<str.length();i++)
{
a[str[i]]++;
}
//第⼆次遍历辅助数组做哈希映射
int pos=-1;
for(int i=0;i<str.length();i++)
{
if(a[str[i]]==1)
{
pos=i;
break;
}
}
cout<<pos<<endl;
return0;
}

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。