0Pricing
Coding Interview Prep · Урок

Группировка и распределение по корзинам с помощью map

Группируйте анаграммы и похожие элементы

«Группировка и распределение по корзинам с помощью map» — бесплатный урок Coding Interview Prep на CoddyKit. Это урок 4 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Coding Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Coding Interview Prep содержит 4 уроков всего.

Группировка — это приём

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

Выбор ключа группировки

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

Корзина со словарём значений по умолчанию

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

from collections import defaultdict
buckets = defaultdict(list)

Основной цикл

Для каждого элемента вычислите его ключ и append элемент в корзину этого ключа. По одной строке на элемент — и всё будет сгруппировано.

for word in words:
    buckets[key_of(word)].append(word)

Группировка анаграмм

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

k = ''.join(sorted(word))
buckets[k].append(word)

Кортежи в качестве ключей количеств

Если сортировка выполняется медленно, в качестве ключа можно использовать и кортеж количеств букв. Кортежи хешируемы, поэтому они без проблем подходят для словаря.

k = tuple(Counter(word)[c] for c in 'abcdefghijklmnopqrstuvwxyz')

Группировка по свойству

Группируйте числа по остатку, чётности или длине, просто меняя ключ. Во всех задачах этот приём остаётся тем же.

for n in nums:
    buckets[n % 3].append(n)

Идея сортировки по корзинам

Если значения лежат в небольшом диапазоне, поместите каждое в индексированную корзину, а затем прочитайте их по порядку. Это сортировка, близкая к линейной.

for x in nums:
    bucket[x].append(x)

Сбор результатов

После распределения по корзинам ответом обычно становятся values словаря. Преобразуйте их в список, если проверяющая система ожидает сами группы.

result = list(buckets.values())

Подсчёт по группам

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

sizes = {k: len(v) for k, v in buckets.items()}

Почему отображение эффективнее

Группировка с помощью отображения занимает O(n), вместо того чтобы сравнивать каждую пару. Хешируемый ключ выполняет сопоставление за вас.

Быстрая проверка

Вы хотите сгруппировать слова так, чтобы анаграммы попадали в одну корзину.

Итоги

Группируйте элементы, сопоставляя ключ каждого элемента с корзиной словаря значений по умолчанию за один проход O(n). Правильно выберите ключ — и задачи на группировку станут намного проще. 🚀

Часто задаваемые вопросы

Урок «Группировка и распределение по корзинам с помощью map» бесплатный?

Да — полный текст урока «Группировка и распределение по корзинам с помощью map» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Coding Interview Prep, подпишись на CoddyKit PRO. Курс Coding Interview Prep содержит 4 уроков всего.

Чему я научусь в уроке «Группировка и распределение по корзинам с помощью map»?

Группируйте анаграммы и похожие элементы Ты практикуешь Coding Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.

Нужен ли мне опыт, чтобы начать Coding Interview Prep?

Предыдущий опыт не требуется. Coding Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 4 из 4.

Сколько времени занимает урок «Группировка и распределение по корзинам с помощью map»?

Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.

Можно ли писать и запускать код в этом уроке Coding Interview Prep?

Да. Каждый урок Coding Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.

Все уроки этого курса

  1. Множества для проверки принадлежности и удаления дублей
  2. Словари как таблицы поиска
  3. Counter и defaultdict в действии
  4. Группировка и распределение по корзинам с помощью map
← Назад к Coding Interview Prep