Как найти самые часто встречающиеся элементы списка в Python

1. Решение с использованием встроенных библиотек Python
2. Решение без Counter
3. Что по производительности и сложности Сравнение методов: как посчитать элементы в списке Python оптимально?

Недавно мне на собеседовании попалась простая, но довольно-таки интересная задача. И связана она снова с нашими любимыми списками.

Поиск самых часто встречающихся элементов в списке — популярная задача на собеседованиях по Python. В этом руководстве разберем два способа её решения.

Задача:

У нас есть целочисленный массив чисел nums = [1, 1, 1, 2, 2, 3, 3, 3, 0, 5]

Этот массив чисел может быть как отсортирован, так и нет. Необходимо написать функцию, которая бы возвращала k = 2 наиболее часто встречающихся элементов в массиве num.

Ожидаемый результат: [1, 3] или [3, 1] — порядок не важен

Пояснения: число 1 встречается 3 раза, число 2 встречается 2 раза, число 3 — 3 раза, число 0 — 1 раз и число 5 тоже 1 раз. Исходя из условия, что число k = 2, ожидается, что нужно найти 2 наиболее часто повторяющихся элемента массива.

Данную задачу можно решить несколькими способами: используя встроенные функции и библиотеки языка Python, а можно решить другим способом — тем самым, которого от вас ожидают на собеседовании. Разберем оба.

Решение с использованием встроенных библиотек Python

# решение с использованием встроенных библиотек Python
from collections import Counter


def top_numbers(nums: list[int], k: int) -> list[int]:
    x = Counter(nums)
    y = x.most_common(k)
    return [i[0] for i in y]

>>> nums = [1, 1, 1, 2, 2, 3, 3, 3, 0, 5]
>>> k = 2
>>> top_numbers(nums=nums, k=k)
[1, 3]

Объяснение:

В этом решении используется встроенная библиотека Python — collections, а конкретно класс Counter. Этот класс специально создан для подсчета количества элементов в списке Python.

from collections import Counter — мы импортируем класс Counter для подсчета частоты элементов последовательности

def top_numbers(nums: list[int], k: int) -> list[int]: — определяем функцию top_numbers, которая принимает на вход список чисел nums и целое число k, и возвращает список наиболее часто встречающихся k чисел

x = Counter(nums) — создаем объект Counter. Теперь x — это словарь, где ключи — это числа из nums, а значения — количество их вхождений. Например, для входного списка [1, 1, 1, 2, 2, 3, 3, 3, 0, 5], x будет выглядеть следующим образом: {1: 3, 2: 2, 3: 3, 0: 1, 5: 1}

y = x.most_common(k) — вызываем метод most_common(k) у объекта x. Этот метод возвращает список из k кортежей, отсортированных по убыванию частоты. Каждый кортеж содержит число и его частоту. Например, если k = 2, для предыдущего примера y будет выглядеть так: [(1, 3), (3, 3)]. (Обратите внимание, что 1 и 3 имеют одинаковую частоту, порядок может быть разным).

return [i[0] for i in y] — используем list comprehension, чтобы извлечь только числа из списка кортежей y. Для каждого кортежа i в y, берем первый элемент i[0] (то есть само число) и добавляем его в новый список. В результате, функция возвращает список из k наиболее часто встречающихся чисел. В нашем примере это будет [1, 3] или [3, 1] (порядок может варьироваться).

Это отличное, читабельное решение, а главное — довольно оптимальное с точки зрения затрат ресурсов на выполнение этой функции.

Решение без Counter

На собеседовании важно не только уметь использовать встроенные методы Python (что является большим плюсом, так как, например, модуль collections часто остается без внимания), но и демонстрировать умение логически рассуждать и применять алгоритмы для решения задач.

Разберем вариант, который чаще всего ожидают услышать на собеседовании:

def top_numbers (nums: List[int], k: int) -> List[int]:
    ct = {}
    for i in nums:
        if i in ct:
            ct[i] += 1
         else:
            ct[i] = 1
        
    items = list(ct.items())
    items.sort(key=lambda item: item[1], reverse=True)
    return [i[0] for i in items[:k]]

Объяснение:

ct = {} — инициализируем пустой словарь ct, который будет хранить частоту каждого числа.

for i in nums: — перебираем все числа в списке nums.

if i in ct: ct[i] += 1 else: ct[i] = 1 — если число i уже есть в словаре ct, увеличиваем его счетчик на 1. В противном случае, добавляем число i в словарь со счетчиком 1. Этот блок кода подсчитывает частоту каждого числа в списке.

items = list(ct.items()) — преобразуем словарь ct в список кортежей items, где каждый кортеж содержит число и его частоту (например, [(1, 3), (2, 2), ...]).

items.sort(key=lambda item: item[1], reverse=True) — сортируем список items по убыванию частоты.

lambda item: item[1] — это анонимная функция, которая возвращает частоту (второй элемент) кортежа, и эта функция используется как ключ для сортировки.

reverse=True указывает на сортировку в порядке убывания.

return [i[0] for i in items[:k]] — извлекаем первые k элементов из отсортированного списка items (то есть k наиболее часто встречающихся чисел) и создаем новый список, содержащий только числа (первые элементы кортежей).

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

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

Что по производительности и сложности

Второй вариант немного сложнее логически, чем первый. В первом варианте Counter «магически» делает подсчет частот за нас, а во втором варианте мы должны реализовать эту логику вручную. Это делает второй вариант более подверженным ошибкам при реализации, если вы не полностью понимаете, что делаете.

Сравнение методов: как посчитать элементы в списке Python оптимально?

Решение	Временная сложность	Пространственная сложность
С Counter	O(N log k)	O(N)
Без Counter	O(N log N)	O(N)

Первый вариант (с Counter): O(N) для подсчета частот + O(N log k) для most_common(k) (в худшем случае, когда все элементы уникальны). Общая временная сложность: O(N log k)
Второй вариант: O(N) для подсчета частот + O(N log N) для сортировки списка items. Общая временная сложность: O(N log N)
Пространственная сложность: Оба варианта имеют пространственную сложность O(N) для хранения частот.

Второй вариант имеет худшую временную сложность (O(N log N)), чем первый вариант (O(N log k)), особенно когда k намного меньше N. Это связано с тем, что второй вариант сортирует все элементы, тогда как Counter.most_common(k) использует алгоритм, который более эффективен для нахождения только k наибольших элементов.

Первый вариант (с Counter) более читаемый и лаконичный. Он выражает намерение кода более четко («подсчитать частоты и взять k самых частых»).

На этом, пожалуй всё, удачных вам интервью и подписывайтесь на наш канал, чтобы оставаться в курсе всего самого свежего!