第一个只出现一次的英文字符

佚名 6年前 (2019-05-16) 随笔 1224人围观抢沙发百度已收录

1、字符串中第一个只出现一次的字符

题目

在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'。

问题分析

需要一个数据容器（哈希表）存放每个字符出现的次数，把一个个字符映射成一个数字。哈希表的键值（Key）是字符，值（Value）是该字符出现的次数。通过2次字符串扫描，第1次进行制作哈希表，第2次每扫描到一个字符，就从哈希表中得到该字符出现的次数。那么，第1个只出现1次的字符就是结果。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

C++标准模板库中的map和unordered_map实现了哈希表功能，但本题较简单，我们可以考虑实现一个简单的哈希表。字符（char）是一个长度为8的数据类型，总共有256中可能。于是，我们创建1个长度为256的数组，每个字母根据ASCII码作为数组下标对应数字的1个数字，而数组中存储的是每个字符出现的次数。这样，我们就创建了1个大小为256、以字符ASCII码为键值的哈希表。

时间复杂度：O（n） --》 2次扫描总次数2 * O（n）

空间复杂度：O（1） --》长度为256的辅助数组，它的大小为1KB，数组大小为常数

详细代码

#include <cstdio>
#include <string>

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

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

    const char* pHashKey = pString;
    while(*(pHashKey) != '\0')
        hashTable[*(pHashKey++)] ++;

    pHashKey = pString;
    while(*pHashKey != '\0')
    {
        if(hashTable[*pHashKey] == 1)
            return *pHashKey;

        pHashKey++;
    }

    return '\0';
}

// ====================测试代码====================
void Test(const char* pString, char expected)
{
    if(FirstNotRepeatingChar(pString) == expected)
        printf("Test passed.\n");
    else
        printf("Test failed.\n");
}

int main(int argc, char* argv[])
{
    // 常规输入测试，存在只出现一次的字符
    Test("google", 'l');

    // 常规输入测试，不存在只出现一次的字符
    Test("aabccdbd", '\0');

    // 常规输入测试，所有字符都只出现一次
    Test("abcdefg", 'a');

    // 鲁棒性测试，输入nullptr
    Test(nullptr, '\0');

    return 0;
}

C++

测试用例

功能测试（字符串中只存在一次的字符；字符串中不存在只出现一次的字符；字符串中所有字符都只出现一次）

特殊输入测试（字符串为nullptr指针）

2、字符流中第一个只出现一次的字符

题目

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是'g'。当从该字符流中读出前六个字符"google"时，第一个只出现一次的字符是'l'。

问题分析

字符只能一个接着一个从字符流中读出来。用字符的ASCII码作为哈希表的键值，而把字符对应的位置作为哈希表的值。当一个字符第一次从字符中读出来时，把它在字符流中的位置保存在数据容器（哈希表）中。当这个字符再次从字符流中读出时，那么它就不是只出现一次的字符，也就可以被忽略了。这是把它在哈希表中保存的值更新为一个特殊的值（如负数值-2）。

详细代码

#include <cstdio>
#include <vector>
#include <limits>

using namespace std;

class CharStatistics
{
public:
    CharStatistics() : index(0)
    {
        for(int i = 0; i < 256; ++i)
            occurrence[i] = -1;  // init: The character has not found;
    }

    void Insert(char ch)
    {
        if(occurrence[ch] == -1)  //第一次从字符流中读出
            occurrence[ch] = index;  //更新为它在字符流中的位置
        else if(occurrence[ch] >= 0) //字符再次从字符流中读出时
            occurrence[ch] = -2;

        index++;
    }

    /* 扫描整个数组，从中找到最小的>=0的值对应的字符 */
    char FirstAppearingOnce()
    {
        char ch = '\0';
        int minIndex = numeric_limits<int>::max();
        for(int i = 0; i < 256; ++i)
        {
            if(occurrence[i] >= 0 && occurrence[i] < minIndex)
            {
                ch = (char) i;
                minIndex = occurrence[i];
            }
        }

        return ch;
    }

private:
    /* occurrence[i]: A character with ASCII value i;
     * occurrence[i] = -1: The character has not found;
     * occurrence[i] = -2: The character has been found for mutlple times
     * occurrence[i] >= 0: The character has been found only once
     */
    int occurrence[256];
    int index;
};

// ====================测试代码====================
void Test(const char* testName, CharStatistics chars, char expected)
{
    if(testName != nullptr)
        printf("%s begins: ", testName);

    if(chars.FirstAppearingOnce() == expected)
        printf("Passed.\n");
    else
        printf("FAILED.\n");
}

int main(int argc, char* argv[])
{
    CharStatistics chars;

    Test("Test1", chars, '\0');

    chars.Insert('g');
    Test("Test2", chars, 'g');

    chars.Insert('o');
    Test("Test3", chars, 'g');

    chars.Insert('o');
    Test("Test4", chars, 'g');

    chars.Insert('g');
    Test("Test5", chars, '\0');

    chars.Insert('l');
    Test("Test6", chars, 'l');

    chars.Insert('e');
    Test("Test7", chars, 'l');

    return 0;
}