题目描述

找出字符串中第一个只出现一次的字符

数据范围：输入的字符串长度满足
1 ≤ string ≤ 1000
1≤n≤1000

输入描述：
输入一个非空字符串

输出描述：
输出第一个只出现一次的字符，如果不存在输出-1

示例1
输入：
asdfasdfo

输出：
o

思路

三种思路

1.暴力求解

即用两层循环(时间复杂度O(N^2))遍历查找
这种方法比较无脑,在面试的时候是在没有思路可以用,这里就不再赘述

2.哈希法

这种有关字符个数的题,都可以使用"哈希法"进行求解,即新建一个数组,以字母的ASCll值为下标,存储数据,每多一个相关字符,该下标的值就加1,最后再遍历一边数组,找到对应值为1(即只出现一次)的字符,找到就直接break或者return,该方法的时间复杂度为O(N)(只是遍历了两次)

#include <iostream>
#include <string>
#include <vector>
using namespace std;void FindFirstChar_1(string& str)
{int Charact[128] = {0};for(int i = 0; i < str.size(); i++){Charact[str[i]]++;}for(int i = 0;i < str.size(); i++){if(Charact[str[i]] == 1){cout << str[i] << endl;return;}}cout << -1 << endl;return;
}
int main() {string str;while(cin >> str){FindFirstChar_1(str);}return 0;
}

3.比较巧妙的方法->string查找函数

在string类中,有两个方法可以使用:find和rfind,分别是正序查找一个字符对应的下标和逆序查找一个字符的下标,容易知道的是,只要两次查找同一字符的下标是相同的,说明整个字符串中该字符只出现了一次:

#include <iostream>
#include <string>
#include <vector>
using namespace std;void FindFirstChar_2(string& str)
{for(int i = 0; i < str.size(); i++){int index1 = str.find(str[i]);int index2 = str.rfind(str[i]);if(index1 == index2){cout << str[i] << endl;return;}}cout << -1 << endl;return;
}int main() {string str;while(cin >> str)FindFirstChar_2(str);return 0;
}