Всем привет!
Возвращаемся к алгоритмам. Сегодня интересная задача среднего уровня.
Есть некоторое распределение людей на группы. Причем нам дан список, в котором индекс соответствует человеку, а значение размеру группы, в которой человек находится. Нужно вернуть распределение людей по группам, то есть список состоящий из списков индексов изначального списка (надеюсь понятно 😄)
Первое время смотрел на задачу, не понимая как за нее взяться. Как распределять индексы по спискам, как определять не превысили ли они предельный размер и т.д. Даже загуглил, как создать пустой список заданного размера (вот так например: n = [None]*10).
Но потом в голове выплыла мысль про словари. Точнее то, что решение большинства алгоритмических задач требует использования словарей (из вот этого видео). И тут дело пошло…
Для начала я сделал пустой словарь.
Далее в цикле добавлял создавал список для каждого размера группы. Если такой ключ (размер группы уже существует), то добавлял значение индекса к этому списку.
После того как словарь готов, то есть все индексы распределены по своим размерам групп, нужно их включить с итоговый список. Но тут проблема, некоторые группы могут быть одинаковыми (в первом примере было две группы по 3 человека). Это приводит к тому, что в словаре эти индексы включены в большой список и его предварительно нужно разбить на несколько частей.
В данном случае, я сделал это в еще одном цикле с помощью срезов списков.
Это решение работало, и даже было достаточно эффективным. Но понятно, что от второго цикла нужно было избавляться
Поэтому я перенес условие про размер группы в перый цикл. Как только длинна списка становится равной соответствующему ключу словаря, список добавляем в ответ, а из словаря удаляем.
И все…
Это решение оказалось не менее эффективным, но тут только один цикл
Я просмотрел другие решения этой задачи. Там было несколько интересных мелочей, которыми можно улучшить решение, но подход остается самым популярным и эффективным.
Из мелочей:
1. можно избавиться от else, если проверять не наличие ключа, а его отсутствие.
2. список из словаря можно удалять разными методами или просто с помощью .pop()
Все на сегодня
До скорого