问题

我正在研究代码信号实践面试问题,我的代码通过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 方法。

  相同标签的其他问题

python-3.xoptimizationmemory