Накопите счётчики в словаре за один проход: для каждого числа увеличивайте значение по его ключу. Это даёт ожидаемое время O(n) и память O(k) для k уникальных чисел.
Функция подсчёта частоты появления чисел в массиве
Накопите счётчики в словаре за один проход: для каждого числа увеличивайте значение по его ключу. Это даёт ожидаемое время O(n) и память O(k) для k уникальных чисел.
Короткий ответ
Что ответить на собеседовании
Подробный разбор
Ответ с пояснениями
Условие
Дан массив, содержащий большое количество целых значений. Требуется реализовать функцию, которая возвращает количество появлений каждого уникального числа в массиве. Например, функция должна принимать список nums и возвращать структуру, где ключом является число, а значением — количество его вхождений.
Ответ
Накопите счётчики в словаре за один проход: для каждого числа увеличивайте значение по его ключу. Это даёт ожидаемое время O(n) и память O(k) для k уникальных чисел.
Реализация работает и с последовательностью, и с одноразовым итератором:
def frequencies(nums):
counts = {}
for number in nums:
counts[number] = counts.get(number, 0) + 1
return counts
Например, [2, 1, 2, 3, 1, 2] превращается в {2: 3, 1: 2, 3: 1}. Пустой вход даёт пустой словарь. Если уникальных значений слишком много для памяти, счётчики нужно агрегировать частями во внешнем хранилище; простой словарь тогда перестаёт быть достаточным решением.