Поиск и подсчёты

К списку можно задать три вопроса, и на каждый есть готовый ответ.

a = [3, 8, 1, 8, 5]

print(8 in a)         # True — есть ли такое значение
print(a.index(8))     # 1 — номер первого вхождения, с нуля
print(a.count(8))     # 2 — сколько раз встречается

Всё это вы уже видели у строк: in, find, count. Разница в одном и важном:

index падает, если элемента нет. Не возвращает −1, как строковый find, а останавливает программу с ошибкой ValueError. Поэтому его либо предваряют проверкой,

if x in a:
    print(a.index(x) + 1)
else:
    print(0)

либо ищут обычным циклом по номерам. Второй способ надёжнее и нужен всё равно: готового «последнего вхождения» у списка нет.

Каждый из трёх вопросов кажется мгновенным, но внутри — обычный проход по списку. x in a перебирает элементы, пока не найдёт; count доходит до конца всегда.

На одном вызове это незаметно. А вот так — уже нет:

for x in a:
    if a.count(x) == 1:      # проход по всему списку на каждом шаге
        ...

Внешний цикл делает $n$ шагов, count внутри — ещё $n$. Итого $n^2$: при ста тысячах элементов это десять миллиардов действий, и решение не проходит.

Ошибка коварна тем, что код выглядит коротким и аккуратным. Вложенности не видно — она спрятана внутри метода.

Правило: готовый метод внутри цикла по тому же списку — почти всегда квадрат. Если такое понадобилось, значит нужен другой приём. Он в следующем блоке.

В списке 100 000 элементов. Сколько примерно действий сделает этот код?

for x in a:
    if a.count(x) > 1:
        ...

Главный приём занятия. Если значения не слишком велики, частоты считаются за один проход.

Идея: завести список, где номер — это само значение, а хранится в нём количество.

table = [0] * 1001          # список из 1001 нуля: для значений от 0 до 1000

for x in a:
    table[x] += 1           # встретили значение x — отметили

print(table[5])             # сколько раз встретилась пятёрка

Запись [0] * 1001 создаёт список нужной длины, заполненный нулями. Один проход по данным — и известны частоты всех значений сразу.

Дальше из таблицы читается почти всё:

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

У массива счётчиков есть цена: его длина равна количеству возможных значений, а не количеству данных.

Для значений от 0 до 1000 таблица занимает тысячу ячеек — ничто. Для значений до миллиона — миллион ячеек, всё ещё приемлемо. А для значений до миллиарда таблицу построить уже нельзя: памяти не хватит.

Поэтому в условиях задач этого занятия ограничение на значения указано отдельно от ограничения на количество — смотрите на него, оно и подсказывает решение:

Третий случай закрывают словари и множества: они считают частоты при любых значениях. До них мы дойдём в модуле про функции и словари, а пока задачи подобраны так, чтобы хватало счётчиков.

И ещё одно. Отрицательные значения индексами быть не могут: table[-3] в Python не ошибка, а обращение с конца списка — то есть тихо неверный ответ. Если в задаче есть отрицательные, их сдвигают: table[x + 1000] += 1.

Значения в списке — целые числа от 0 до 100 включительно.

Сколько ячеек должно быть в массиве счётчиков? Введите целое число.

Таблица на единицу короче. Для значений от 0 до $m$ нужно $m + 1$ ячеек. Признак: list index out of range ровно на самом большом значении.

index без проверки. Элемента нет — программа падает с ValueError. Признак: падение на тестах, где искомого значения не оказалось.

Порядок перепутан. «Первое неповторяющееся значение» — это первое по списку, а не наименьшее. Если пройти таблицу счётчиков, получится наименьшее — другой ответ. Нужны два прохода: сначала частоты, потом список в исходном порядке.

Как проверять себя

• все элементы одинаковые — различное значение одно, частота максимальная;
• все элементы разные — каждая частота равна единице;
• искомого нет — что выводится по условию;
• крайние значения: 0 и верхняя граница диапазона — они проверяют размер таблицы.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Первые задачи решаются готовыми средствами, дальше почти везде выручает массив счётчиков. Обращайте внимание на ограничение значений: именно оно говорит, какой длины делать таблицу и годится ли она вообще.

В одной задаче со звёздочкой значения намеренно велики, а список короток — там счётчики не построить, и перебор пар оказывается уместным. Это не поблажка, а часть навыка: выбирать приём по ограничениям.

Задача: «дан список из $n$ чисел, $n$ до $10^5$, значения от 0 до 1000; выведите, сколько значений встречается ровно один раз».

Ученик написал:

n = int(input())
a = list(map(int, input().split()))
count = 0

for x in a:
    if a.count(x) == 1:
        count += 1

print(count)

Решение верное и короткое, но получает превышение времени. Объясните, где спрятана вложенность, оцените количество действий и предложите решение, которое пройдёт.