题目的主要信息:
这道题比较简单,主要就是找到字符串中第一个只出现一次的字符。
方法一:
string中本身存在两个函数find_first_of和find_last_of,这两个函数可以查找当前字符在字符串中第一次和最后一次出现的位置。这两个函数可以用来判断字符是否只出现一次,如果第一次出现的位置和最后一次出现的位置相同,则表示这个字符只出现了一次。我们可以遍历一遍字符串,这样第一次找到的只出现一次的字符就是第一个。
具体做法:
#include <string>
#include <iostream>
using namespace std;
int main()
{
string str;
while(cin >> str)
{
bool flag = false;//flag用来判断是否存在只出现一次的字符
for(int i =0;i<str.size();i++)//遍历一遍字符串
{
if(str.find_first_of(str[i]) == str.find_last_of(str[i]))//判断当前字符是否是只出现了一次
{
cout << str[i] << endl;//若是,则输出这个字符
flag = true;
break;//找到了第一次出现的字符,跳出循环
}
}
if(!flag) cout << "-1" << endl;//如果没有找到第一次出现的字符,则输出-1
}
return 0;
}
复杂度分析:
- 时间复杂度:,遍历一遍字符串。
- 空间复杂度:,只用了常数空间。
方法二:
除了string中的函数,我们也可以用频数统计法。首先遍历一遍字符串,用一个大小为26的数组来统计字符串中各字符出现的频数。统计完频数后,再遍历一遍字符串,从数组中找到当前字符的频数,若为1,则输出该字符。 具体做法:
#include <iostream>
#include <string>
using namespace std;
int main()
{
string str;
while(cin>>str)
{
int count[26] = {0};
for(int i = 0; i < str.size(); i++)//统计每个字符出现的频数
{
count[str[i] - 'a']++;
}
bool flag = false;//用户判断是否存在只出现一次的字符
for(int i = 0; i < str.size(); i++)
{
if (count[str[i] - 'a'] == 1)//判断当前字符是否只出现一次
{
cout<<str[i]<<endl;
flag = true;//改变flag
break;
}
}
if(!flag){//若flag为false表示存在只出现一次的字符
cout<<-1<<endl;
}
}
return 0;
}
复杂度分析:
- 时间复杂度:,需要遍历字符串。
- 空间复杂度:,count是固定长度的数组,只占用常数空间。