Представьте полку с книгами, среди которых есть пустые места (нули). Вы хотите сдвинуть все книги влево, плотно, а пустоты — вправо. Вы ведёте пальцем-указателем pos по полке, отмечая «куда поставить следующую книгу». Идёте по полке, и каждую найденную книгу ставите на позицию пальца, сдвигая палец дальше. В конце оставшиеся места заполняете пустотами.
Условие
Дан списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list.nums. Переместите все нули в конец, сохранив порядок ненулевых элементов. Менять нужно тот же список (на месте) и вернуть его.
Пример: [0, 1, 0, 3, 12] → [1, 3, 12, 0, 0].
Идея: два указателя
Заводим указатель pos — позицию, куда положить очередное ненулевое число. Идём по списку; встретив ненулевой элемент, ставим его на pos и сдвигаем pos. В конце оставшиеся места заполняем нулями.
▶ move-zeroes.py
Разбор
pos = 0 — «палец»: индексНомер позиции элемента в последовательности. В Python нумерация с нуля: первый элемент — индекс 0., куда поставить следующий ненулевой элемент.
Первый циклКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно.: для каждого ненулевого x записываем его в nums[pos] и сдвигаем палец pos += 1.
После первого цикла все ненулевые стоят слева по порядку, а pos указывает, где начинается «хвост».
Второй цикл range(pos, len(nums)) заполняет хвост нулями.
💡Совет
Приём «указатель записи» pos — частый шаблон: один проход собирает «нужные» элементы в начало списка. Так же решаются «удалить дубликаты из отсортированного массива» и «удалить элемент».
💡Совет
🔮 Предскажите вывод
Что получится из [4, 0, 5, 0, 0, 7] после move_zeroes? Сначала выпишите ненулевые по порядку, затем добавьте нужное число нулей.
▶ predict-zeroes.py
Ответ — [4, 5, 7, 0, 0, 0]. Ненулевые по порядку: 4, 5, 7 (палец дошёл до индекса 3). Остаток (индексы 3, 4, 5) заполнен тремя нулями.
⚠️ Частые ошибки новичков
Частая ошибка — забыть второй цикл, который дозаполняет хвост нулями. Тогда в конце списка останутся «старые» значения, которые мы не перетёрли. Запустите сломанный код: ненулевые сдвинутся, но нули в конце не появятся, и порядок будет неверным.
▶ broken-zeroes.py
Заданиелёгкаярешение.py
Реализуйте move_zeroes(nums): переместите нули в конец, сохранив порядок остальных. Верните изменённый список.
Заданиелёгкаярешение.py
Дополнительное упражнение тем же приёмом. Напишите remove_value(nums, val), которая собирает в начало списка все элементы, не равныеval, и возвращает их количество k (как в LeetCode «Remove Element»). Первые k элементов списка должны быть «оставшимися».
❓Проверь себя
Что хранит указатель pos в приёме «указатель записи»?
Почему такой алгоритм называют «на месте» (in-place)?
ℹ️Важно
✅ Что вы узнали
«Указатель записи» pos собирает нужные элементы в начало списка за один проход.
Это работает «на месте» — без создания нового списка (O(1) доп. памяти).
Тот же шаблон решает «удалить элемент» и «убрать дубликаты».
Комментарии
Загрузка…
Загрузка комментариев…