Задача на перемещение нулей в конец списка

Прошло уже достаточно много времени с предыдущего поста (если быть точнее, то почти год🙂). Пора освежить блог и написать что-нибудь полезное для собратьев программистов.

Итак, сегодня разберем задачу на перемещение нулей в конец списка (массива). Хоть решение таких задач не особо важно на практике, но лично мне пригодилось для прохождения интервью (да-да, там иногда приходиться решать задачки ;-)). 

Переходим к описанию задачи:

Имеется список: [1, 0, 9, 6, 0, 12, 3]

Задача: переместить все нули в конец списка

Входные данные:

[1, 0, 9, 6, 0, 12, 3]

Выход:

[1, 9, 6, 12, 3, 0, 0]

Давайте подумаем, как сие дело решить🧐. Наверняка первое, что приходит в голову, это пройтись по всему массиву дважды (как в сортировке пузырьком) и переместить наши нолики в конец. Такой жесткий "брут форс" навряд ли можно назвать эффективным решением (так что сразу же отбросьте этот способ). И уж тем более когда вы решаете задачу на интервью такой подход сильно снизит ваши шансы на прохождение оного. 

Для решения данной задачи за линейное время нам пригодится *барабанная дробь динамическое программирование. На самом деле очень полезная вещь, когда необходимо сократить время решения подобных задач (ну и ещё этим можно потешить свое самолюбие😄). 

Чтобы решить нашу задачку, необходимо использовать указатели. Нам потребуется только один указатель, который будет (простите за тафталогию) указывать на последний НЕНУЛЕВОЙ элемент массива. На рисунках ниже показан принцип работы алгоритма.

Итак, очень надеюсь, что картинки немного разъяснили суть алгоритма. Напоследок код данного алгоритма на Python:

Ну что ж, подведем итог нашего разбора этой, на первый взгляд, простой задачи. При решении подобного рода задач всегда есть место творчеству и то, как вы решаете задачи, показывает не только ваш "скилл", но и насколько далек полет вашей фантазии 😉. Решение задачек прокачивает мозги, а их разбор ещё и помогает лучше понять работу различных алгоритмов. 

Так что желаю вам наращивать свои мозговые мускулы и наслаждаться коддингом!