第十七题（找出字符串中第一个只出现一次的字符）

本文主要是介绍第十七题（找出字符串中第一个只出现一次的字符），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff，则输出b

o(n^2)时间复杂度的方法比较简单，遍历每一个字符，将其和后面的每个字符进行比较，若没有相同的，那么这个字符就是要寻找的字符。

要实现更低阶的时间复杂度，我们可以采用空间换时间的思想，采用哈希表解决这个问题。利用一次循环统计每个字符出现的次数，然后找出出现次数为1的字符即可，哈希表的键为字符，值为字符对应的出现次数。

这里给出分别用stl的unordered_map和自定义哈希表的实现的代码：

#include<unordered_map>
#include<iostream>
using namespace std;
namespace MS100P_17
{//采用stl的unordered_mapunordered_map<char,int>	charMap;char firstSingle(char* str){int length = strlen(str);for (int i = 0; i < length; i++)charMap[str[i]]++;for (int i = 0; i < length;i++)if (charMap[str[i]] == 1)return str[i];return '\0';		//未找到}char firstSingle2(char* str){int hash[256];memset(hash, 0, 256*sizeof(int));for (int i = 0; i < strlen(str); i++)hash[str[i]]++;for (int i = 0; i < strlen(str);i++)if (hash[str[i]] == 1)return str[i];return '\0';		//未找到}void test(){char str[] = "abaccdeff";cout << firstSingle(str) << endl;cout << firstSingle2(str) << endl;}
}int _tmain(int argc, _TCHAR* argv[])
{MS100P_17::test();return 0;
}

这篇关于第十七题（找出字符串中第一个只出现一次的字符）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---