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

Question

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

Answer 1

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

因此,您可以迭代字符并在第一次看到它时将每个字符附加到列表中,并分别记录您看到它的次数(事实上,对于计数而言唯一重要的值是"0" ,"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)中运行.

Answer 2

在处理完整个字符串之前,你不可能知道字符是不重复的,所以我的建议是这样的:

def first_non_repeated_character(string):
  chars = []
  repeated = []
  for character in string:
    if character in chars:
      chars.remove(character)
      repeated.append(character)
    else:
      if not character in repeated:
        chars.append(character)
  if len(chars):
    return chars[0]
  else:
    return False

编辑:最初发布的代码很糟糕,但这个最新的片段是Ryan的计算机™认证工作.