Алгоритмы на Python. 24 задачи с решениями и проверками

│print('OK: задача 4')

После успешных проверок: OK: задача 4

Почему это работает

В примере правый склад даёт два разрешения для b и по одному для a и d. Первый b забирает одно, затем a расходует своё. Второй b расходует последнее разрешение b. Для c запаса нет; второй a и третий b тоже пропускаются. Неиспользованное разрешение d не создаёт элемент ответа, потому что в left нет соответствующей позиции. Получается [b, a, b].

Инвариант: remaining[x] равно частоте x в right минус число уже выбранных x из обработанного префикса left. Остаток не бывает отрицательным, поскольку уменьшение разрешено только после проверки на положительность. Одновременно result является подпоследовательностью просмотренной части left. Значит, ни допустимое количество, ни исходный порядок не могут нарушиться на очередном шаге.

Для каждой строки алгоритм берёт её появления, пока не закончится либо левый вход, либо запас правого. Число взятых равно минимуму частот, что и требуется от пересечения мультимножеств. Выбор ранних появлений следует из единственного левого обхода: при наличии разрешения отказа нет. Counter возвращает ноль для отсутствующего ключа, поэтому отдельная ветка для неизвестной этикетки не нужна. Чтение такого значения не расходует память на все строки из left.

Время и память

n = len(left), m = len(right), u — число разных строк right. В среднем O(n + m) хеш-операций, O(u) дополнительной памяти без ответа. Это средняя, не худшая оценка хеш-таблицы; при коллизиях возможно O((n + m)²) сравнений. Стоимость обработки символов длинных строк учитывается отдельно.

Типичная ошибка

Использовать пересечение set(left) & set(right): оно теряет кратность и не задаёт нужного порядка. Проверка item in right без уменьшения запаса, наоборот, пропустит слишком много копий.

Измените условие

Можно ли переставить left и right для экономии памяти?

Разбор вопроса

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

Конец ознакомительного фрагмента.

Текст предоставлен ООО «Литрес».

Прочитайте эту книгу целиком, купив полную легальную версию на Литрес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.