我面临的问题是在O(1)复杂度的列表中查找/检查项目.以下具有O(n)的复杂性:
'foo' in list_bar
这具有O(n)的复杂性,因为您in在a 上使用关键字list.(参考Python时间复杂度)
但是,如果in在a上使用关键字set,则其复杂度为O(1).
我需要弄清楚列表的O(1)复杂性而不是集合的原因主要是由于需要考虑列表中的重复项.集不允许重复.一个很好的例子是:
chars_available = ['h', 'e', 'l', 'o', 'o', 'z']
chars_needed = ['h', 'e', 'l', 'l', '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 False
foo(chars_available, chars_needed)
这个例子不是重点,所以请尽量不要偏离它.重点仍然是试图在列表中查找项目时获得O(1)复杂性.我怎么能蟒蛇化？
(作为额外的功劳,如果您确实希望以Python,伪代码或其他语言显示更好的方式来执行该操作,我将很乐意阅读它).
谢谢!
编辑:
为了回应Ami Tavory的回答,我了解到你不能比O(n)更快地制作列表,但是建议collections.Counter()帮助解决我正在研究的应用程序.我正在为Stack Overflow上传我更快的解决方案,性能非常出色!如果我没有弄错(如果我错了,请纠正我),它应该是O(1),因为它只涉及可散列值而没有循环迭代.
from collections import Counter
chars_available = ['h', 'e', …