ЕГЭОГЭЕНТ
РУҚА
Тапсырмалар № 19, 26 · ЕГЭ

Словарь частот

Структура данных для подсчёта повторений значений
2 мин чтенияҚиындық: Обновлено 29 қыркүйек 2026

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

Словарь частотНазвание связано с обычным словарём: по ключу-значению находят соответствующее число.
Словарь частот — это набор пар «значение — число появлений». Ключом служит само значение, а значением словаря — его частота, то есть количество вхождений. Например, для массива \([2, 5, 2, 2, 5]\) словарь частот имеет вид: \(2 \to 3\), \(5 \to 2\).

Словарь частот строят последовательным перебором строки или массива. Для каждого элемента увеличивают счётчик с этим ключом на единицу. Если ключ встречается впервые, его начальный счётчик считают равным нулю, а затем увеличивают. Такая структура является программным вариантом таблицы частот.

Как строится словарь частот

\[f(x)=\left|\{i\mid a_i=x\}\right|\]

Здесь \(f(x)\) — частота значения \(x\), а \(a_i\) — элемент массива с индексом \(i\). Чтобы получить частоты всех значений, достаточно один раз просмотреть \(n\) элементов. В среднем операция увеличения счётчика занимает постоянное время, поэтому построение словаря обычно имеет сложность \(O(n)\).

№
Пример

Для строки banana последовательно учитываем символы: b встречается 1 раз, a — 3 раза, n — 2 раза. Итоговый словарь: {b: 1, a: 3, n: 2}. Если требуется найти самый частый символ, сравнивают значения счётчиков.

!
Не путайте

Словарь частот хранит частоту каждого значения, а относительная частота показывает его долю среди всех элементов: \(f(x)/n\). Кроме того, словарь не обязан сохранять порядок появления значений.

Проверьте себя

Какой будет частота символа о в строке молоко?

Главное за минуту

Главное

  • Словарь частот сопоставляет каждому значению число его появлений.
  • Его строят одним перебором массива или строки, увеличивая счётчик каждого ключа.
  • Частота — абсолютное количество появлений; доля от общего числа называется относительной частотой.