由网友(心疼无法治愈)分享简介：什么是最好的空间和时间，有效的解决方案，以找到像 aabccbdcbe ？字符串的第一个非重复字符这里的答案为d。所以这令我的一点是，它可以通过两种方式来完成：对于每一个指标i循环时，i-1次，检查是否曾经再次出现该字符。但是，这是没有效率：此方法的生长为O（N ^ 2）其中N是串的长度。 另一种可能的好办法可能是，...

什么是最好的空间和时间，有效的解决方案，以找到像 aabccbdcbe ？

字符串的第一个非重复字符

这里的答案为d。所以这令我的一点是，它可以通过两种方式来完成：

对于每一个指标i循环时，i-1次，检查是否曾经再次出现该字符。但是，这是没有效率：此方法的生长为O（N ^ 2）其中N是串的长度。 另一种可能的好办法可能是，如果我能形成一个树或使得我可以命令字符基于所述权重（所述出现计数）任何其他的ds。这可能需要我长N只是一个遍历字符串组成的结构。这仅仅是O（N）+ O（时间来建立树或任何DS）。 解决方案

下面是一个非常简单的 O（N）解决方法：

  DEF FN（S）：
  为了= []
  计数= {}
  对于x在S：
    如果x的罪状：
      计数[X] + = 1
    其他：
      计数[X] = 1
      order.append（X）
  对于x依次是：
    如果计数[X] == 1：
      返回X
  返回None
 

通过串一旦我们循环。当我们遇到一个新的角色，我们将其存储在计数与 1 的值，并追加到序。当我们遇到我们以前见过一个角色，我们增加了在值计数。最后，我们通过序，直到我们找到 1 的值的字符计数循环返回。

What would be the best space and time efficient solution to find the first non repeating character for a string like aabccbdcbe?

The answer here is d. So the point that strikes me is that it can be done in two ways:

For every index i loop i-1 times and check if that character occurs ever again. But this is not efficient: growth of this method is O(N^2) where N is the length of the string. Another possible good way could be if I could form a tree or any other ds such that I could order the character based on the weights (the occurrence count). This could take me just one loop of length N through the string to form the structure. That is just O(N) + O(time to build tree or any ds).

解决方案

Here's a very straightforward O(n) solution:

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

We loop through the string once. When we come across a new character, we store it in counts with a value of 1, and append it to order. When we come across a character we've seen before, we increment its value in counts. Finally, we loop through order until we find a character with a value of 1 in counts and return it.