Программирование Вызов кода занимает слишком много времени

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) 

Но код производит Лимит времени Exceeded Error. Раньше я пытался использовать in для каждого предмета в студенте, но он создал TLE, и я считаю, что это потому, что оператор in равен O(n). Итак, я написал этот код, требуемые шаги которого примерно равны сумме длин обоих списков. Но это также производит TLE. Итак, какие изменения я должен внести в свой код. Есть ли какая-то особенная часть, которая имеет высокие затраты времени?

Спасибо.

Answer 1

Вы используете сортировку + слияние. Это требует сложности времени O(NlogN + MlogM + N + M).

Но вы можете поместить данные профессоров в set, проверьте каждое значение года студент (из несортированный списка) и получить O(M + N) сложность (в среднем).

Обратите внимание, что этот подход исключает длительную сортировку списка учеников.

Дополнение: python имеет встроенные наборы. Для языков, которые не имеют такого положения, список профессоров уже отсортирован, поэтому вы можете использовать бинарный поиск каждый год. Сложность будет O(NlogM).

Answer 2

Поскольку проблема в принципе найти пересечение двух наборов целых чисел следующий код решает эту проблему в O(M + N) при предположении, что словарь возможен доступ в O(1)

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

equals_dates = len(prof.intersection(student))