Что не так с алгоритмом?

Question

[Dauren S]

Добрый день, тестер показывает якобы неверно.Что не так?
Задача:
На вход программе подается большое количество целых чисел. Все числа, кроме одного, имеют пару, причем может быть несколько одинаковых пар. Найдите число без пары.

def test(a): 
  for index,n in enumerate(a): 
    if(a.count(n)%2!=0): 
      return n 
a=[1,1,2,2,3,3,4,4,5,5,6,6,7,7,1]
print(test(a))

Ограничение времени 1 секунда
Ограничение памяти 64Mb
Ввод стандартный ввод или input-201.txt
Вывод стандартный вывод или input-201.a.txt
Может с вводом что то не то?
Время у меня 44ms
Память 3.96Mb

Comments

[kunjut19]

def test(arr):
for index,n in enumerate(arr):
может, из-за этого?

[Dauren S]

kunjut19, Спасибо, поправил. Но не из за этого.

Answer 1

[Алексей Уколов]

тестер показывает якобы неверно

Скорее всего, по времени не укладываетесь. Сейчас у вас алгоритм очень неоптимальный - вы делаете в худшем случае n² итераций по массиву (count же тоже должен как-то посчитать значения). Раз в тексте задачи специально уточняется про большое количество чисел, подразумевается, что алгоритм будет максимально нежадным по ресурсам.

Можно сэкономить время, потратив немного памяти, и обойтись двумя итерациями - в первой подсчитать количество каждого числа (через инкремент в специальном словаре, а не count), а во второй найти нечётное количество.

Comments

[Dauren S]

Спасибо, буду думать.

[Dauren S]

Компилятор Вердикт Тип посылки Время Память Тест Баллы
26 май 2020, 18:22:08
33247805
A
Python 3.7.3
WA
-
44ms
3.98Mb
1

[Алексей Уколов]

Что это значит?

Answer 2

[Константин]

- `enumerate(a)` создаёт копию поля
- `arr` не используется вообще
- функция `test` возможно изолированна от `а`
- `index` не использован

Answer 3

[galaxy]

Классическая задача на алгоритмы в вакууме.

spoiler

Числа можно просто поксорить

Comments

[Константин]

Спойлер: Сортировка n*log(n), память n

https://docs.python.org/3/library/heapq.html