dauren101
@dauren101
Python, PHP developer

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

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

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
  • Вопрос задан
  • 246 просмотров
Решения вопроса 1
тестер показывает якобы неверно
Скорее всего, по времени не укладываетесь. Сейчас у вас алгоритм очень неоптимальный - вы делаете в худшем случае n2 итераций по массиву (count же тоже должен как-то посчитать значения). Раз в тексте задачи специально уточняется про большое количество чисел, подразумевается, что алгоритм будет максимально нежадным по ресурсам.

Можно сэкономить время, потратив немного памяти, и обойтись двумя итерациями - в первой подсчитать количество каждого числа (через инкремент в специальном словаре, а не count), а во второй найти нечётное количество.
Ответ написан
Пригласить эксперта
Ответы на вопрос 2
- `enumerate(a)` создаёт копию поля
- `arr` не используется вообще
- функция `test` возможно изолированна от `а`
- `index` не использован
Ответ написан
@galaxy
Классическая задача на алгоритмы в вакууме.
spoiler
Числа можно просто поксорить
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы
Poteha Labs Москва
от 100 000 до 160 000 ₽
МТС Москва
от 150 000 до 250 000 ₽
iCode Москва
от 90 000 до 200 000 ₽