algorithm - 查找字符串中第一个未重复的字符

Question

找到字符串中只出现一次的第一个字符的最快方法是什么？

Answer 1

它必须至少为 O(n)，因为在阅读完所有字符之前，您不知道一个字符是否会重复。

所以你可以遍历字符并在你第一次看到它时将每个字符附加到一个列表中，并分别记录你看到它的次数(事实上，唯一对计数重要的值是“0”、“1”或“多于 1”)。

当您到达字符串的末尾时，您只需找到列表中第一个计数正好为 1 的字符。

---

Python 示例代码:

def first_non_repeated_character(s):
    counts = defaultdict(int)
    l = []
    for c in s:
        counts[c] += 1
        if counts[c] == 1:
            l.append(c)

    for c in l:
        if counts[c] == 1:
            return c

    return None

这在 O(n) 中运行。