如何在Python中更高效地找到首个不重复字符？

云原生阿岚

2026-6-1

O(n)时间复杂度的首个不重复字符查找函数

原代码的性能问题

你写的代码逻辑正确，但时间复杂度为O(n²)——因为每次循环调用s.count(c)时，都会完整遍历一遍整个字符串。当字符串长度较大（比如上万字符）时，这种嵌套遍历会导致运算量激增，效率极低。

优化方案（O(n)时间复杂度）

通过两次线性遍历实现高效查找：

第一次遍历：统计每个字符的出现次数（用哈希表/字典存储）
第二次遍历：再次遍历原字符串，找到第一个出现次数为1的字符

实现代码（两种方式）

方式1：使用`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

方式2：手动用字典统计（无需额外导入）

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

优化后的优势

时间效率：两次遍历都是线性的，总时间复杂度为O(n)。对比原代码的O(n²)，当字符串长度为10^{4时，原代码需要10}8次操作，优化后仅需2*10^4次，性能提升几个数量级。
空间开销：哈希表存储的是字符的出现次数，而字符集的大小是固定的（比如英文字母仅26个，Unicode常用字符数量也远小于字符串长度），因此空间复杂度可视为O(1)（常数级）。