欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

面试题:第一次只出现一次的字符

程序员文章站 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

下一篇: