Блог

Я учусь писать на python с помощью этого веб-сайта, используя HankerRank. Я столкнулся с этой проблемой, и код, который я написал, не прошел несколько тестов из-за превышения лимита времени. Поэтому я зашел на YouTube и использовал учебник, и его код работал, но я не понимаю, почему его код более эффективен, чем мой. Если кто-нибудь сможет объяснить, я буду вам очень признателен.

Мой Код:

 room=list(map(int, input().split()))
room.sort()
roomset=set(room.copy())

for i in roomset:
    if room.count(i)!=K:
        print(i)
    else:
        continue
 

Код учебника:

 room=list(map(int, input().split()))
room.sort()
a=set()
b=set()

for i in room:
    if i not in a:
        a.add(i)
        b.add(i)
    else:
        b.discard(i)
        
for o in b:
    print(o)
 

Причина, по которой ваш код работает медленно, заключается в том, что на каждой итерации вашего цикла python должен сканировать весь список, чтобы подсчитать, сколько раз появляется это число. Это означает, что в худшем случае количество операций растет с квадратом размера ввода, что занимает много времени.

Код учебника просто содержит набор чисел, которые встречались по крайней мере один раз ( a ), и набор чисел, которые встречались ровно один раз ( b ). Все операции набора для вставки, удаления и проверки принадлежности являются постоянными по времени, поэтому время их алгоритма линейно увеличивается с длиной входных данных.

Потому что для цикла и комнаты.count(i) дает O(n) * O(n) = O(n**2) временную сложность. В то время как учебное решение равно O(n)

Превышение времени означает, что вы выполняете больше работы, чем требуется.

room.sort() — зачем вам sort список номеров комнат? Код не использует никаких преимуществ этого. (странно, другой код делает то же самое, я что-то упустил?)

roomset=set(room.copy()) — нет необходимости делать копию

Но главная проблема в том, что вопрос не в том, сколько раз номер комнаты присутствует в списке?, а точнее: это точно 1?. Если вы сталкиваетесь с номером комнаты во второй раз, у вас есть ответ, и вы должны прекратить считать.

Более эффективный код делает именно это. Он запоминает, видел ли он номер комнаты (набор a ) и было ли это первое появление (набор b ). Никакого подсчета, т. е. достаточно просмотреть список всего один раз — это важное повышение эффективности. После изучения всех чисел набор b содержит только элементы с ровно одним появлением.