我在尝试写一个Python函数，返回字符串中第一个不重复的字符。 例如：

• "leetcode" → "l"
• "loveleetcode" → "v"
• "aabb" → None

我希望解法高效（最好是O(n) 时间复杂度）。

下面是我尝试过的：

def first_unique_char(s):
    for c in s:
        if s.count(c) == 1:
            return c
    return None

它能工作，但我觉得对于很长的字符串效率不高。 能否帮我优化这个并解释为什么改进后的版本更好？

解决方案

在你的代码中，你是逐个字符地查看（这是一个O(n) 的操作，其中n 是输入字符串的长度），然后再统计该字符在字符串中出现的次数。为了得到这个计数，你还需要再次查看每个字符（也是一个O(n) 的操作）。

因此，算法的时间复杂度是O(n**2)，因为我们对同一个操作执行了n 次。

在下面的代码中，我们逐个遍历每个字符，并递增我们已经看到的该字符的出现次数。为此我们使用 collections.Counter 类，它是 dict 的一个子类。这是一个O(n) 的操作，其中n 是实参 s 的大小。

然后逐一查看每个字符及其计数，直到找到一个计数为1 的字符并返回该字符。如果找不到这样的字符，我们返回 None。这同样也是一个O(n) 操作。因此我们连续执行了两个O(n) 操作，即O(n) + O(n)，总体仍然是O(n)。

from collections import Counter


def first_unique_char(s):
    counts = Counter(s);
    for ch, count in counts.items():
        if count == 1:
            return ch
    return None

for s in (
    'leetcodee',
    'loveleetcode',
    'aabb'
):
    print(repr(s), '->', repr(first_unique_char(s)))

输出：

leetcodee' -> 'l'
'loveleetcode' -> 'v'
'aabb' -> None

更新：适用于Python 3.7及以下版本

有人指出，键的插入顺序只有在Python 3.7及以上版本中才会得到保证。如果你使用的版本比它更早，那么：

from collections import OrderedDict


def first_unique_char(s):
    counts = OrderedDict();
    for ch in s:
        count = counts.get(ch, 0)
        count += 1
        counts[ch] = count

    for ch, count in counts.items():
        if count == 1:
            return ch
    return None

for s in (
    'leetcodee',
    'loveleetcode',
    'aabb'
):
    print(repr(s), '->', repr(first_unique_char(s)))

对于上述实现，对输入字符串中的每个字符，执行两次字典查找：一次用于获取当前计数（可能不存在），一次用于更新自增计数。这里有另一种实现，使用 setdefault 方法和一个 OrderedDict 实例，将每个输入字符的查找次数降至一次，但代价是分配新的 Counter 实例。不过，我们能够将类 Counter 的实例化次数控制在n + 1，其中n 是字符串s 中不同字符的数量。这在长字符串且重复字符很多的情况下应该比之前的算法更快。

from collections import OrderedDict


def first_unique_char(s):
    class Counter:
        def __init__(self):
            self.count = 0

    counts = OrderedDict();
    unused_counter = Counter()

    for ch in s:
        char_counter = counts.setdefault(ch, unused_counter)
        char_counter.count += 1
        if char_counter is unused_counter:
            unused_counter = Counter()

    for ch, counter in counts.items():
        if counter.count == 1:
            return ch
    return None

for s in (
    'leetcodee',
    'loveleetcode',
    'aabb'
):
    print(repr(s), '->', repr(first_unique_char(s)))