查找字符串中第一个不重复字符的最佳方法

Question

要找到像 aabccbdcbe 这样的字符串中第一个不重复的字符，最好的方法是什么，既省空间又省时间呢？

答案是字符 d。让我想到的是，这个问题可以用两种方式来解决：

1. 第一种方法是，对于每个字符的索引 i，循环检查它前面的所有字符，看看这个字符是否还出现过。这种方法效率不高，因为它的复杂度是 O(N^2)，也就是说，如果字符串变长，所需的时间会迅速增加。
2. 第二种更好的方法是，如果我能构建一个树或者其他数据结构，这样我就可以根据字符出现的次数来排序。这种方法只需要一次遍历整个字符串，复杂度是 O(N)，再加上构建树或其他数据结构所需的时间。

Answer 1

我觉得从字符串中去掉重复的字符，可以大大减少操作的次数。举个例子：

s = "aabccbdcbe"
while s != "":
    slen0 = len(s)
    ch = s[0]
    s = s.replace(ch, "")
    slen1 = len(s)
    if slen1 == slen0-1:
        print ch
        break;
else:
    print "No answer"

Answer 2

列表推导式可以让你得到字符，顺序和它们出现的顺序一样，如果每个字符只出现一次：

In [61]: s = 'aabccbdcbe'

In [62]: [a for a in s if s.count(a) == 1]
Out[62]: ['d', 'e']

然后只需要返回这个结果的第一个元素：

In [63]: [a for a in s if s.count(a) == 1][0]
Out[63]: 'd'

如果你只需要第一个元素，使用生成器也可以：

In [69]: (a for a in s if s.count(a) == 1).next()
Out[69]: 'd'

Answer 3

这里有一个非常简单的 O(n) 解决方案：

def fn(s):
  order = []
  counts = {}
  for x in s:
    if x in counts:
      counts[x] += 1
    else:
      counts[x] = 1 
      order.append(x)
  for x in order:
    if counts[x] == 1:
      return x
  return None

我们只需遍历这个字符串一次。当我们遇到一个新字符时，就把它存到 counts 里，值设为 1，同时把它添加到 order 里。如果遇到一个之前见过的字符，就把它在 counts 里的值加一。最后，我们再遍历 order，直到找到一个在 counts 里值为 1 的字符，然后返回这个字符。