我撰寫的以下演算法查找字串中的第一個非重復字符，并回傳其索引或 -1（如果沒有）：
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
它的空間復雜度是否為 O(1)，因為您可以在堆疊或重復串列中擁有 O(26) 個元素，但不能同時擁有兩者？
uj5u.com熱心網友回復：
是的，space complexity您的程式額外消耗的是O(1)，因為無論輸入大小如何，資料結構最多可以包含 26 個元素。
再一次，你的time complexitywill be 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 的變數實際上并不是 astack并且某些操作似乎是多余的。您可以使用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，即字母表中的字符數。
轉載請註明出處，本文鏈接：https://www.uj5u.com/shujuku/313560.html
上一篇：生成以前不存在于串列中的亂數
下一篇：紅黑樹的性質