C++:使用哈希映射的第一个非重复字符,O(n)时间

Question

我正在尝试编写一个函数来获取字符串的第一个非重复字符.对于所有情况,我都没有在O(n)时间内找到令人满意的答案.我目前的解决方案是:

char getFirstNonRepeated(char * str) {
    if (strlen(str) > 0) {
        int visitedArray[256] = {};    // Where 256 is the size of the alphabet
        for (int i = 0; i < strlen(str); i++) {
            visitedArray[str[i]] += 1;
        }

        for (int j = 0; j < 256; j++) {
            if (visitedArray[j] == 1) return j;
        }

    }
    return '\0';    // Either strlen == 0 or all characters are repeated
}

但是,只要n <256,该算法在最坏的情况下在O(n ^ 2)时间内运行.我已经读过使用散列表而不是数组来存储每个字符被访问的次数可以让算法在O(n)时间内一致地运行,因为哈希表的插入,删除和搜索在O中运行(1次.我没有找到解释如何正确执行此操作的问题.我没有很多在C++中使用哈希映射的经验,所以任何帮助都会受到赞赏.

Answer 1

为什么要在每个循环中重复调用strlen()？这与字符串的长度呈线性关系,因此您的第一个循环实际上变为O(n ^ 2),完全没有任何理由.只需计算一次长度并存储它,或使用str [i]作为结束条件.

您还应该知道,如果您的编译器使用有符号字符,则任何大于127的字符值都将被视为负数(并用作负数,即超出界限,数组偏移量).您可以通过显式地将字符值转换为unsigned char来避免这种情况.