假设我有一个包含以空格分隔的不重复整数的输入。在这种情况下,使用下面的内容,
比下面这种方法快吗?如果是(我实际上就是这样经历过的),为什么呢?
请阅读输入时不要专注于没有到 int 的转换这一事实。
在我正在处理的一个问题中,使用 list() 会导致超时,但是通过使用 set(),我可以使它在时间限制内运行。我想知道这是为什么?
编辑:如果可能相关的话,以下是相关代码。
setA = set(input().split())
比下面这种方法快吗?如果是(我实际上就是这样经历过的),为什么呢?
listA = list(input().split())
请阅读输入时不要专注于没有到 int 的转换这一事实。
在我正在处理的一个问题中,使用 list() 会导致超时,但是通过使用 set(),我可以使它在时间限制内运行。我想知道这是为什么?
编辑:如果可能相关的话,以下是相关代码。
arr = input().split()
for ele in arr:
if ele in setA:
happiness += 1
elif ele in setB:
happiness += -1
else:
pass
当 arr
是一行用空格分隔的整数时,这次没有唯一性。
set
中成员检查需要O(1)
的时间,而在list
中需要O(n)
的时间。 - Ch3steRset
是使用hashtables
实现的。为了检查成员身份,基本上只需要查看该对象是否位于由其哈希确定的位置即可,因此此操作的速度不取决于集合的大小。相反,对于列表来说,需要搜索整个列表,随着列表增长,这将变得更慢。 - Ch3steR