面试题35：第一个只出现一次的字符

本文链接：https://blog.csdn.net/kekong0713/article/details/52458870

本文介绍了一种高效的算法，用于从字符串中查找第一个仅出现一次的字符。通过构建256大小的数组来记录每个字符出现的次数，实现了O(n)的时间复杂度和O(1)的空间复杂度。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

1。在字符串中找出第一个只出现一次的字符。例如输入“abaccdeff”,则输出‘b’

分析：

考虑到是字符串，字串中的字符只有256中情况，因此可以构建一个这样大小的数组来记录每个字符出现的次数，以字符串中出现的字符为数组的下标，遍历一次字符串就可以统计出字符串中每个字符出现的次数。然后再次遍历字符串，去改数组中找对应的出现的次数，如果次数为1，则返回在字符。这样的时间复杂度是2*O(n),也就是O(n)，空间复杂度是O(256),因为是常数，可以认为是O(1)。在字符串比较短的情况下，会存在空间的少许浪费，但是在字符串比较长的情况下，效果就很明显了。

源码：

/**
		* 功能说明：找出字符串中第一次只出现一次的字符
		* 作者：K0713
		* 日期：2016-9-6
		**/
#include<iostream>
#include <string>
using namespace std;

char FirstNotRepeatingChar(char* pString)
{
	if (pString == NULL)
		return '\0';

	const int tableSize = 256;
	unsigned int hashTable[tableSize];
	for (unsigned int i = 0; i<tableSize; ++i)
		hashTable[i] = 0;

	char* pHashKey = pString;
	while (*(pHashKey) != '\0')//第一遍统计每个字符出现的次数
		hashTable[*(pHashKey++)] ++;

	pHashKey = pString;//第二遍遍历字符串，然后在哈希表中找对应的次数
	while (*pHashKey != '\0')
	{
		if (hashTable[*pHashKey] == 1)
			return *pHashKey;

		pHashKey++;
	}

	return '\0';
}

int main()
{
	char* testString = "abaccdeff";
	char result = FirstNotRepeatingChar(testString);
	cout << "the first not repeating char is: " << result << endl;
	system("PAUSE");
	return 0;
}