我正在研究代码信号实践面试问题,我的代码通过16/19测试,但由于超过允许的时间限制,其余测试失败.
我尝试使用set()而不是列表,但是计数方法不起作用,因为我对python非常新,我不知道更好的替代方案.
def firstNotRepeatingCharacter(s):
list = []
num = '_'
for i in s:
list.append(i)
for i in list:
if list.count(i) <= 1:
num = i
return num
return num
如果您正在使用Python 3.7,其中dict键为insertion-order,您可以使用collections.Counter:
from collections import Counter
def firstNotRepeatingCharacter(s):
return next((char for char, count in Counter(s).items() if count == 1), '_')
使用先前版本的Python,您可以使用collections.OrderedDict来跟踪计数:
from collections import OrderedDict
def firstNotRepeatingCharacter(s):
counts = OrderedDict()
for char in s:
counts[char] = counts.get(char, 0) + 1
return next((char for char, count in counts.items() if count == 1), '_')
所以firstNotRepeatingCharacter('aababdcbcea')返回:'d'
上述两个代码片段都具有 O(n) 的时间复杂性,而 O(n ^ 2) 在您的解决方案中是由于在循环中使用 list.count 方法。