面试题35：第一个只出现一次的字符
题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b。(2006年google的一道笔试题。)
分析：
首先应向确认一下是ASCII字符串，而不是Unicode字符串。用hash表求解即可，由于需要先遍历一次，时间复杂度为O(n)，空间复杂度为O(1) (256个ASCII字符).
满足题意的代码如下：
#include<cstdio>
#include<string>
#include<unordered_map>
using namespace std;
class Solution {
public:
char FirstNotRepeatingChar(string str) {
if(str.size() == 0) return '\0';
unordered_map<char, int> countMap; // 使用C++中的map的insert时，返回结果是自动按key排序(增序)后的结果
for(int i = 0;i < str.size();i++){
if(countMap.find(str[i]) == countMap.end())
countMap[str[i]]=1;
// countMap.insert({str[i], 1}); // 映射表中没找到相关记录，加到映射表，次数设置为1
else countMap[str[i]]++; // 映射表中找到了相关记录，将映射表中的次数+1
}
// int pos = -1;
char ch;
for(int i = 0;i < str.size();i++){
if(countMap[str[i]] == 1){
// pos = i;
ch=str[i];
break;
}
}
return ch;
}
};
// 以下为测试
int main()
{
Solution sol;
string str1="abaccdeff";
string str2="cbacnba";
char res1 = sol.FirstNotRepeatingChar(str1);
char res2 = sol.FirstNotRepeatingChar(str2);
printf("%c\n", res1);
printf("%c\n", res2);
return 0;
}也可简化为：
#include<cstdio>
#include<string>
#include<unordered_map>
using namespace std;
class Solution {
public:
char FirstNotRepeatingChar(string str) {
int hash[256] = {0};
for(auto c : str){ // 遍历一次，复杂度为O(n)
hash[c] ++;
}
char ch;
for(int i=0;i<str.size();i++){
if(hash[str[i]] == 1){
//return i;
return str[i];
}
}
return '\0'; // if(str.size() == 0) return '\0';
}
};
// 以下为测试
int main()
{
Solution sol;
string str1="ABACCDEFF";
string str2="cbacnba";
char res1 = sol.FirstNotRepeatingChar(str1);
char res2 = sol.FirstNotRepeatingChar(str2);
printf("%c\n", res1);
printf("%c\n", res2);
return 0;
}相比而言，前一种方法更高效，256个字符可能只出现很少的一部分，后面这种方法在空间上消耗多一点...
九度OJ 提交网址 http://ac.jobdu.com/problem.php?pid=1283
牛客网OJ 改编： 在一个字符串(1<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符的位置。若为空串，返回-1。位置索引从0开始。
提交网址： http://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187
- 输入：
-
一个字符串。
- 输出：
-
输出第一个只出现一次的字符下标，没有只出现一次的字符则输出-1。
- 样例输入：
- ABACCDEFF
AA
- 样例输出：
- 1
-1 - 牛客网 AC代码：
class Solution {
public:
int FirstNotRepeatingChar(string str) {
if(str.size() == 0) return -1;
unordered_map<char, int> countMap; // 使用C++中的map的insert时，返回结果是自动按key排序(增序)后的结果
for(int i = 0;i < str.size();i++){
if(countMap.find(str[i]) == countMap.end())
countMap[str[i]]=1; // 映射表中没找到相关记录，加到映射表，次数设置为1
else countMap[str[i]]++; // 映射表中找到了相关记录，将映射表中的次数+1
}
int pos = -1;
for(int i = 0;i < str.size();i++){
if(countMap[str[i]] == 1){
pos = i;
break;
}
}
return pos;
}
};精简之后：
class Solution {
public:
int FirstNotRepeatingChar(string str) {
int hash[256] = {0};
for(auto c : str){ // 遍历一次，复杂度为O(n)
hash[c] ++;
}
for(int i=0;i<str.size();i++){
if(hash[str[i]] == 1){
return i;
}
}
return -1; // if(str.size() == 0) return -1;
}
};华为OJ034-找出字符串中第一个只出现一次的字符
时间限制：1秒 空间限制：32768K 参与人数：157
本题知识点： 字符串
题目描述
找出字符串中第一个只出现一次的字符
接口说明
原型：
char FindChar(InputString);
输入参数：字符串InputString
输出参数：
如果无此字符 请输出该字符；如果无此字符，请输出'.'。
输入描述
输入一串字符
输出描述
输出一个字符
输入例子
asdfasdfo
输出例子
o
AC代码(C++风格)：
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
char FirstNotRepeatingChar(string str)
{
if(str.size() == 0) return '.';
unordered_map<char, int> countMap;
for(int i = 0;i < str.size();i++){
if(countMap.find(str[i]) == countMap.end())
countMap[str[i]]=1;
else countMap[str[i]]++; // 映射表中找到了相关记录，将映射表中的次数+1
}
char ch;
for(int i = 0;i < str.size();i++){
if(countMap[str[i]] == 1){
ch=str[i];
break;
}
}
return ch;
}
int main() {
string str;
while(cin>>str) {
char ch=FirstNotRepeatingChar(str);
cout<<ch<<endl;
}
return 0;
}或
#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;
char FindChar(string str)
{
unordered_map<char,int> m;
char ch;
for(unsigned int i=0; i<str.size(); i++)
m[str[i]]++;
unsigned int i;
for(i=0; i<str.size(); i++) {
if(m[str[i]]==1) {
ch=str[i]; break;
}
}
if(i==str.size()) ch='.';
return ch;
}
int main() {
string str;
while(cin>>str) {
char ch=FindChar(str);
cout<<ch<<endl;
}
return 0;
}AC代码(使用指针)：
#include<iostream>
#include<string>
using namespace std;
char FindChar(char *input)
{
char *p=input;
int hash[256];
for(int i=0;i!=256;i++)
hash[i]=0;
while(*p!='\0')
{
hash[*p]++;
p++;
}
char *p1=input;
while(*p1!='\0')
{
if(hash[*p1]==1)
{
return *p1;
}
p1++;
}
return '.';
}
int main()
{
char str[1000];
while(cin>>str)
{
char ch=FindChar(str);
cout<<ch<<endl;
}
return 0;
}