move_zeroes.md

Передвинуть нули в конец массива

Условие

Дан массив целых чисел. Требуется передвинуть все нули в конец. Функция должна принимать массив целых чисел и менять его содержимое.

Примеры

[-1, 0, 2, 5, 8]

Ответ: [-1, 2, 5, 8, 0]

[0, 2, 1, 4, 5]

Ответ: [2, 1, 4, 5, 0]

Решение

Заведем переменную, которая будет служить индексом, на который нужно поставить ненулевой элемент. Начальное значение будет 0.

Затем, пройдемся по всему массиву. Если текущий элемент массива ненулевой, это значит, что мы должны поставить его на указанный индекс, а сам индекс увеличить на один.

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

public class Solution {
    public static void moveZeroesToEnd(int[] numbers) {
        int insertIndex = 0;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != 0) {
                numbers[insertIndex++] = numbers[i];
            }
        }

        while (insertIndex < numbers.length) {
            numbers[insertIndex++] = 0;
        }
    }
}

Время работы: O(N + K), где N - длина массива, K - количество нулей в массиве

Память: O(1)