我是一个初学者,正在练习有关hackerrank的问题。
我编写此代码是作为问题的一部分,该问题因大量输入而超时:
K = int(input())
roomnos = input().split()
setroomnos = set(roomnos)
for r in setroomnos:
if roomnos.count(r) == 1:
print(r)
break
下一个被法官接受所有测试用例
K = int(input())
roomnos = [int(i) for i in input().split()]
setroomnos = set(roomnos)
c = (K * sum(setroomnos) - sum(roomnos)) // (K - 1)
print(c)
您能否解释一下为什么第一个超时输入大量内容而第二个却正常工作
PS:基本操作是找到一个在列表中仅出现一次的编号,而不是其他出现K次的编号
最佳答案
您的第一个解决方案使用O(n)for
,其中包含O(n)count
-导致O(n ^ 2)复杂性。您的第二个示例不以这种方式嵌套操作,O(n)复杂度也是如此。