我为 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。那么,我应该对我的代码进行哪些更改。是否有一些特定的部分时间成本高?
谢谢。
最佳答案
您正在使用排序+合并。这需要 O(NlogN + MlogM + N + M)
时间复杂度。
但您可以将教授数据放入集合
,检查每个学生年份值(来自未排序列表)并得到O(M + N)
复杂度(平均)。
请注意,这种方法消除了学生列表排序的冗长操作。
补充:python有内置集合。对于没有这种规定的语言,教授的列表已经排序,所以你可以使用每年的二进制搜索。复杂度为 O(NlogM)
。
关于python - 编程挑战代码花费太多时间,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36937362/