时间戳

首页 > 解决方案 > 如何最大化python效率？

python-3.x - 如何最大化python效率？

问题描述

我正在处理一个代码信号练习面试问题，我的代码通过了 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.xoptimizationmemory

解决方案

如果您使用的是 Python 3.7+，其中 dict 键是按插入顺序排列的，您可以使用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

推荐阅读