学步园

我们可以定义一个哈希表，让键为字符，而值是该字符出现的次数，我们扫描两次字符串，第一次扫描统计每个字符出现的字符，第二次从头扫描找出只出现了一次的字符。

代码如下：

#include<iostream>
using namespace std;
char First(char*);
int main()
{
    char number[10]={'a','b','a','c','c','d','e','f','f'};
    cout<<First(number);
    return 0;
}
char First(char *pstring)
{
    if(pstring==NULL)
        return '\0';
    const int table_size=256;
    unsigned int HashTable[table_size];
    for(int i=0;i<table_size;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';
}

如果字符串的长度为n，则第一次扫描的时间复杂度为O(n),在第二次扫描时，同样O(1)能读出一个字符出现的次数，所以时间复杂度还是O(n)。这样总的时间复杂度还是O(n)，同时我们需要使用一个包含256个字符的辅助数组，大小为1k,由于这个数组的大小为常数，所以可以认为它的空间复杂度是O(1).

Reference

《名企面试官精讲典型编程题》 何海涛