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 '';    // 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 的字符值都将被视为负数（并用作负数，即越界、数组偏移量）。可以通过将字符值显式转换为无符号字符来避免这种情况。