C++:第一个非重复字符，使用 HashMap 的 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(n) 时间内运行(1次。我还没有找到解释如何正确执行此操作的问题。我没有太多在 C++ 中使用 HashMap 的经验，因此任何帮助将不胜感激。

Answer 1

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

您还应该注意，如果您的编译器使用有符号字符，则任何高于 127 的字符值都将被视为负数(并用作负数，即越界、数组偏移量)。您可以通过将字符值显式转换为 unsigned char 来避免这种情况。