python - 编程挑战代码花费太多时间

Question

我为 this problem. 编写了以下代码

prof = sorted([int(input()) for x in range(int(input()))])
student = sorted([int(input()) for x in range(int(input()))])

prof_dates = len(prof)
stud_dates = len(student)

amount = 0

prof_index = 0
stud_index = 0

while stud_index < stud_dates and prof_index < prof_dates:
    if student[stud_index] == prof[prof_index]:
        amount += 1
        stud_index += 1

    elif student[stud_index] > prof[prof_index]:
        prof_index += 1

    elif student[stud_index] < prof[prof_index]:
        stud_index += 1


print(amount)

但是代码产生了超出时间限制的错误。早些时候，我曾尝试对学生中的每个项目使用 in，但它产生了一个 TLE，我相信那是因为 in 语句是 O(n)。因此，我编写了这段代码，其所需的步骤大致等于两个列表的长度之和。但这也产生了 TLE。那么，我应该对我的代码进行哪些更改。是否有一些特定的部分时间成本高？

谢谢。

Answer 1

您正在使用排序+合并。这需要 O(NlogN + MlogM + N + M) 时间复杂度。

但您可以将教授数据放入集合，检查每个学生年份值(来自未排序列表)并得到O(M + N) 复杂度(平均)。

请注意，这种方法消除了学生列表排序的冗长操作。

补充:python有内置集合。对于没有这种规定的语言，教授的列表已经排序，所以你可以使用每年的二进制搜索。复杂度为 O(NlogM)。