如何在Python中更高效地查找第一个不重复字符？求O(n)时间复杂度的优化方案及原理

嘿，你的思路方向是对的，但确实如你所说，这段代码在处理长字符串时效率会拉胯——问题出在每次调用的s.count(c)上。咱们先拆解下原代码的问题，再给出O(n)级的优化方案。

原代码的效率瓶颈 #

你当前的代码里，每循环一个字符就调用s.count(c)，而这个方法会完整遍历整个字符串来统计该字符的出现次数。假设字符串长度是n，那总操作次数就是n×n，时间复杂度直接来到O(n²)。当字符串很长（比如上万字符）时，这个重复遍历的开销会非常大。

优化方案：两次线性遍历实现O(n)时间复杂度 #

我们可以把操作拆成两步：先遍历一次字符串统计所有字符的出现频率（这一步是O(n)），再遍历一次字符串找第一个频率为1的字符（这一步也是O(n)），总时间复杂度就是O(n)，空间复杂度属于常数级（因为英文字母最多26个，ASCII字符最多128个，完全不会占用过多内存）。

方法1：用普通字典手动统计 #

def first_unique_char(s):
    char_count = {}
    # 第一次遍历：统计每个字符的出现次数
    for c in s:
        char_count[c] = char_count.get(c, 0) + 1
    # 第二次遍历：找到第一个出现次数为1的字符
    for c in s:
        if char_count[c] == 1:
            return c
    return None

方法2：用collections.Counter简化代码 #

Python标准库的collections.Counter已经封装了字符频率统计的逻辑，用它能让代码更简洁，效率和手动字典几乎一致：

from collections import Counter

def first_unique_char(s):
    char_count = Counter(s)
    for c in s:
        if char_count[c] == 1:
            return c
    return None

为什么这个优化更优？ #

• 时间效率：整个过程只需要两次线性遍历字符串，总时间是O(n)。对比原代码的O(n²)，在处理大字符串时速度提升非常明显——比如n=10000时，原代码要做1亿次操作，优化后只需要2万次。
• 空间效率：我们只需要存储字符串中不同字符的计数，对于英文字符串来说最多26个键，属于常数级空间O(1)，完全不用担心内存压力。就算处理Unicode字符，不同字符的数量通常也远小于字符串长度，空间开销依然可控。

测试你的示例场景：

• "leetcode" → 统计后l:1, e:3, t:1...，第一个次数为1的是l，结果正确。
• "loveleetcode" → 统计后v是第一个出现次数为1的字符，结果正确。
• "aabb" → 所有字符次数都是2，返回None，结果正确。

内容的提问来源于stack exchange，提问作者user32642875