Space 第一个非重复字符算法的复杂度

Question

我编写的以下算法查找字符串中的第一个非重复字符和 returns 其索引或 -1 如果有 none:

def firstNonRepeatingCharacter(string):
    stack = []
    repeats = []
    for char in string:
        if char in stack:
            del stack[stack.index(char)]
            repeats.append(char)
        elif char not in stack and char not in repeats:
            stack.append(char)
    if len(stack) > 0:
        return string.index(stack[0])
    return -1

它的 space 复杂度是否为 O(1)，因为您可以在堆栈或重复列表中包含 O(26) 个元素，但不能同时包含两者？

Answer 1

是的，您的程序消耗的额外 space complexity 是 O(1)，因为无论输入大小如何，数据结构最多可以包含 26 个元素。
同样，由于内部循环，您的 time complexity 将是 O(n)，而不是 O(n^2)。

for char in string:   # O(n) - n being the number of characters in your string
   if char in stack:  # O(1) since stack can have at most 26 characters
      del stack[stack.index(char)] 
      repeats.append(char)
   elif char not in stack and char not in repeats:  # O(1) since stack and repeats can have at most 26 characters
      stack.append(char)
   if len(stack) > 0:
      return string.index(stack[0])

如评论中所述，您名为 stack 的变量实际上不是 stack 并且某些操作似乎是多余的。您可以使用 dict.

更有效地实施相同的过程

def firstNonRepeatingCharacter(string):
    dict_ = {}
    for idx in range(len(string)):   # n many iterations
        char = string.lower()[idx]
        dict_[char] = len(string) if (char in dict_) else idx
    
    idx = min(dict_.values()) # dict_ can have at most 26 elements - O(1)
    return -1 if(idx == len(string)) else idx

firstNonRepeatingCharacter("aabc")

请记住，由于使用了哈希函数，x in dict 操作平均需要 O(1)。字典的长度也最多为 26，字母表中的字符数。

Space 第一个非重复字符算法的复杂度

Space complexity of first non-repeating character algorithm

python

algorithm

data-structures

space-complexity