Ссылка на задачу:
🔗 https://leetcode.com/problems/move-zeroes
Задача под номером 283 (Move Zeroes) на платформе LeetCode — классическая задача на работу с массивами. Она нередко появляется в различных технических собеседованиях и тренировочных курсах. Несмотря на свою простоту, она требует понимания оптимальных подходов к работе с массивами "внутри".
🧩 Условие задачи:
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
Note that you must do this in-place without making a copy of the array.
На русском:
Дано: массив целых чисел nums.
Нужно: переместить все нули в конец массива, сохранив относительный порядок остальных (ненулевых) элементов.
Важно: модифицировать массив нужно "на месте" (то есть in-place), без создания копий массива.
Примеры:
Пример 1:
Input: [0, 1, 0, 3, 12]
Output: [1, 3, 12, 0, 0]
Пример 2:
Input: [0]
Output: [0]
Перед тем как посмотреть решение, подумайте как бы вы решали такую задачу?
Подписывайтесь на мой канал в Телеграмм, чтобы ничего не пропустить.
Ну или на канал в VK, если хотите видеть новые статьи у себя в ленте.
💡 Решение: Алгоритм двух указателей (Two Pointers)
Ваш подход к решению задачи — оптимальный. Он использует технику "двух указателей", где один указатель (last_non_zero) отслеживает позицию, куда нужно переместить следующий ненулевой элемент, а второй (i) итерирует весь массив.
Решение на Python:
🔍 Как работает этот алгоритм?
- Переменная last_non_zero обозначает индекс, куда должен быть помещён следующий ненулевой элемент.
- Если текущий элемент не равен 0, мы меняем его местами с элементом по индексу last_non_zero, даже если это один и тот же элемент (в этом случае "обмен" не повлияет на массив).
- После перестановки, двигаем указатель last_non_zero вправо.
- По завершении цикла, все ненулевые элементы уже в начале массива, а нули автоматически "отправлены" в конец.
📈 Почему этот алгоритм лучший?
- Временная сложность: O(n) — мы проходим массив один раз (n — длина массива).
- Пространственная сложность: O(1) — т.к. не создаём дополнительных структур данных; все манипуляции происходят in-place.
- Общее количество операций минимально, т.к. перестановки происходят только при обнаружении ненулевого элемента. В случае, если массив уже отсортирован (нули в конце), перестановок не будет вообще.
🧠 Альтернативные (но менее эффективные) подходы:
- Создать новый массив для хранения ненулевых элементов и затем добавить соответствующее количество нулей. ⛔ Но это нарушает условие задачи — нельзя использовать дополнительную память.
- Удалять все нули и дополнять массив на место. Также неэффективно по времени из-за временных затрат на insert/delete.
Спасибо, что прочли до конца 🙌
Подписывайтесь на мой канал в Телеграм или в VK — впереди ещё много интересного про ИИ, NLP и тестирование!
До встречи в следующих статьях! 💡