大多数Pythonic方法在O(1)复杂度的列表中查找检查项目？

概述我面临的问题是在O(1)复杂度的列表中查找/检查项目.以下具有O(n)的复杂性： 'foo' in list_bar 这具有O(n)的复杂性,因为您在列表中使用了in关键字. (参见Python Time Complexity) 但是,如果在集合上使用in关键字,则其复杂度为O(1). 我需要弄清楚列表的O(1)复杂性而不是集合的原因主要是由于需要考虑列表中的重复项目.集不允许重复.一个很好的例子 我面临的问题是在O(1)复杂度的列表中查找/检查项目.以下具有O(n)的复杂性：

'foo' in List_bar

这具有O(n)的复杂性,因为您在列表中使用了in关键字. (参见Python Time Complexity)

但是,如果在集合上使用in关键字,则其复杂度为O(1).

我需要弄清楚列表的O(1)复杂性而不是集合的原因主要是由于需要考虑列表中的重复项目.集不允许重复.一个很好的例子是：

chars_available = ['h','e','l','o','z']chars_needed = ['h','o']def foo(chars_available,chars_needed):    cpy_needed = List(chars_needed)    for char in cpy_needed:        if char in chars_available:            chars_available.remove(char)            chars_needed.remove(char)        if not chars_needed: return True  # if chars_needed == []    return Falsefoo(chars_available,chars_needed)

这个例子不是重点,所以请尽量不要偏离它.重点仍然是试图在列表中查找项目时获得O(1)复杂性.我怎么能Python化？

(作为额外的功劳,如果您确实希望以Python,伪代码或其他语言显示更好的方式来执行该 *** 作,我将很乐意阅读它).

谢谢！

编辑：

为了回应Ami Tavory的回答,我了解到你不能比O(n)更快地创建列表,但对collections.Counter()的建议帮助解决了我正在处理的应用程序.我正在为Stack Overflow上传我更快的解决方案,性能非常出色！如果我没有弄错(如果我错了,请纠正我),它应该是O(1),因为它只涉及可散列值而没有循环迭代.

from collections import Counterchars_available = ['h',chars_needed):    counter_available = Counter(chars_available)    counter_needed = Counter(chars_needed)    out = counter_needed - counter_available    if not List(out.elements()): return True    else: return Falsefoo(chars_available,chars_needed)

非常快,非常pythonic！谢谢！

解决方法 通常,不可能在恒定时间内在列表中找到元素.您可以假设维护列表和集合,但更新 *** 作将花费线性时间.

你提到你的动机是

a List,and not a set,is largely due to the need to account for duplicate items within the List. Sets do not allow for duplicates.

并要求不要专注于这个例子.如果这是你的动机,你可能想要使用而不是一个集合,一个dict将每个元素映射到它的出现次数.

您可能会发现collections.Counter特别有用：

In [1]: from collections import CounterIn [2]: Counter(['h','z'])Out[2]: Counter({'e': 1,'h': 1,'l': 1,'o': 2,'z': 1})

总结

以上是内存溢出为你收集整理的大多数Pythonic方法在O(1)复杂度的列表中查找/检查项目？全部内容，希望文章能够帮你解决大多数Pythonic方法在O(1)复杂度的列表中查找/检查项目？所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。