如何提高python代码的时间效率?

你应该考虑你的解决方案的复杂性(这是非常糟糕的):

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))。这不是一个很好的复杂性。你需要一个在输入中是线性的复杂度。有两种方法:

1. 使用哈希表标记所有访问的整数,并且 set 是这样一个哈希表。不幸的是哈希表有一些缺点。
2. 既然有 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)

n = '5'
i = '2 5 5 1 1'

def compute(n, i):
    s1 = set(range(1, n+1))
    yield from sorted(s1.difference(i))


for val in compute(int(n), map(int, i.split()) ):
    print(val, end=' ')

印刷品:

3 4 

关键是使用一个集合来检查输入字符串中是否存在预期的数字。不过,您不需要将输入转换为整数。另一种方法是将序列号生成为字符串。

nums    = input().split()
numSet  = set(nums)
missing = " ".join(str(n) for n in range(1,len(nums)+1) if str(n) not in numSet)

print(missing) # 3 4

对于这个特定的问题,有一个比使用集合更快的选择,因为您可以创建一个具有已知(和合理)大小的标志数组:

numbers = input().split()
present = [False]*len(numbers)
for n in numbers: present[int(n)-1] = True
missing = " ".join(str(n+1) for n,seen in enumerate(present) if not seen)

您将希望将现有的数字转换为 int 埃格斯,然后把它们放在 set ;集合对于计算给定值是否为成员非常有效。

n = int(input())
extant = set(int(n) for n in input().split())
for i in range(1, n + 1):
    if i not in extant:
        print(i, end=" ")