Переместите нули

Сложность: 🟢 Легкая

ℹ️ Описание

Вам дан целочисленный массив nums. Переместите в нём все нули в конец, сохраняя относительный порядок ненулевых элементов.

Обратите внимание, что вы должны сделать это in-place, не копируя массив.

⚠️ Ограничения

— Длина массива от 1 до 10000 элементов
— Каждый элемент массива может принимать значение в диапазоне от -2^31 до 2^31 - 1

1️⃣ Пример

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

nums = [0,1,0,3,12]

Ответ

[1,3,12,0,0]

2️⃣ Пример

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

nums = [0]

Ответ

[0]

✅ Решение

Решение задачи крайне простое.

Нам нужно завести два индекса. Первый — обычный индекс i, который инкриминируется на каждой итерации. Второй firstZeroIndex — индекс первого нулевого элемента в массиве, который изначально равен 0.

Далее мы итерируемся по всем элементам массива и, как только встречаем ненулевой элемент, меняем его местами с нулем, который стоит под индексом firstZeroIndex. Дополнительно увеличиваем firstZeroIndex, если произошла перестановка.

Таким образом все нули будут «всплывать» в конец массива за один проход..

Посмотреть реализацию в блоге

🅾️ Оценка сложности

По времени

Сложность O(n), так как мы итерируемся по всем элементам массива.

По памяти

Сложность O(1), так как мы не выделяем дополнительную память, зависящую от длины массива.

#arrays #easy