口试系列(1)-哈希表查找字符串中第一次仅出现一次的字母

面试系列(1)--哈希表查找字符串中第一次仅出现一次的字母

/***********************************************************************
问题：在一个只有大小写字符串中查找第一个只出现一次的字母
input: aacddcvghhgii
output: v
思路：使用hashtable 来使得时间复杂度为O(n) 
	  创建hashtable 
**********************************************************************/
#include <stdio.h>
#include <string.h>
#include <ctype.h>
//哈希函数 返回索引地址
int HashFunction(char ch)
{
	if(islower(ch))
		return ch-'a';
	else 
		if(isupper(ch))
			return 26+ch-'A';
}

void MapHashTable(char HashTable[],char a[],int len)
{
	int pos;
	for(int i=0;i<len;i++)
	{
		pos=HashFunction(a[i]);
		//if(HashTable[pos]==0) //表明未被赋值
			++HashTable[pos];
	}
}
char HashSearch(char HashTable[],char a[],int len)
{	
	int pos;
	for(int i=0;i<len;i++)
	{
		pos=HashFunction(a[i]);
		if(1==HashTable[pos])
		{	
			if( 26<=pos && pos<=51)
				return pos-26+'A';
			else 
				return pos+'a';
		}
	}
	return -1; //未找到符合题意
}
int main()
{
	char str[]="aacddcBvghhAgii";
	int len=strlen(str);
	printf("源字符串为:%s\n",str);
	char HashTable[52]; //哈希表 用于存储次数
	memset(HashTable,0,sizeof(HashTable)/sizeof(char));
	MapHashTable(HashTable,str,len);
	char ch=HashSearch(HashTable,str,len);
	if(ch!=-1)
		printf("第一次只出现一次的字符为:%c\n",ch);
}