你应该考虑你的解决方案的复杂性(这是非常糟糕的):
def modusoperandi(n, t):
# Since 't' is a tuple, the complexity of 'not in t' is O(len(t))
# This makes the overall complexity of this function O(len(t))
if str(n) not in t:
yield n
n = int(input())
t = tuple(sr for sr in input().split()) # O(len(t))
for i in range(1,n+1): # O(n) iterations
# 0 or 1 iteration, but the call to 'modusoperandi' is O(len(t))
for j in modusoperandi(i,t):
print(j,end=' ')
总复杂度o(n*len(t))。这不是一个很好的复杂性。你需要一个在输入中是线性的复杂度。有两种方法:
-
使用哈希表标记所有访问的整数,并且
set
是这样一个哈希表。不幸的是哈希表有一些缺点。
-
既然有
n
条目和数字在1..n范围内,那么使用特征向量是非常有效的
values_encountered
,其中
values_encountered[i]
是
True
如果且仅当
i
遇到值。对于这种类型的大输入,这种解决方案可能比集合运行得更快,并且消耗更少的内存。
是的。
import numpy as np
n = int(input())
values_encountered = np.zeros(n+1, dtype=bool) # O(n)
values_encountered[[int(i) for i in input().split()]] = True # O(n)
# Or:
# values_encountered[list(map(int, input().split()))] = True
values_missing= (values_encountered == False) # O(n)
values_missing[0] = False
print(*list(*values_missing.nonzero())) # O(n)
