面试题:第一次只出现一次的字符
程序员文章站
2024-03-16 20:50:16
...
题目描述:在字符串中找到第1个只出现一次的字符。如输入“abaccdeff”,则输出‘b’.
思路(1):从头开始扫描字符串中的字符,并与后面的字符比较,若未发现相同的字符,则该字符为第一次出现的字符,打印之时间复杂度为O(n*n),故不推荐该种做法!
思路(2):哈希表,从头扫描字符串两次,第一次扫描时,每扫描到一个字符就将哈希表的对应项中次数加1.第二次扫描时,每扫描到一个字符就可从哈希表中得到该字符出现的次数。故只出现一次的字符为所需字符,打印即可,此种算法时间复杂度为O(n)。
代码实现:
#include <iostream>
using namespace std;
#include <windows.h>
#include <assert.h>
#include "Test.h"
#define tablesize 256//哈希表大小
//在字符串中找到第1个只出现一次的字符。如输入“abaccdeff”,则输出‘b’.
char FirstAppearChar(char* str)
{
if (str == NULL)
{
return'\0';
}
//创建一个哈希表,并初始化为0
unsigned int HashTable[tablesize] = { 0 };
//第一次扫描字符串,哈希表相应位置加1
char* tmp = str;
while (*(tmp) != '\0')
{
HashTable[(*tmp++)]++;//各自的ASCII值作下标
}
//第二次扫描字符串
tmp = str;
while (*tmp != '\0')
{
//查找字符出现次数
if (HashTable[*tmp] == 1)
return *tmp;
tmp++;
}
return '\0';//未找到
}
int main()
{
char *str = "abaccdeff";
char tmp = FirstAppearChar(str);
printf("%c\n", tmp);
system("pause");
return 0;
}
上一篇: skui skia-m85