Сдвиг нулей

Постановка задачи

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

[1, 3, 12, 0, 0]

Решение

Эта задача на модификацию массива "на месте" - фундамент для решения более сложных задач на два указателя. На интервью она часто кажется обманчиво простой, и именно в этом кроется ловушка. Вот основные моменты, на которых кандидаты "плывут":

• Самая частая ошибка: создание дополнительного массива, чтобы скопировать туда все ненулевые числа, а потом заполнить остаток нулями. Это требует O(n) дополнительной памяти.

• Решение в два прохода: сначала сдвигаем все ненулевые элементы вперед, а потом вторым циклом заполняем хвост массива нулями. Если в массиве почти все нули, например [0, 0, 0, ..., 1], будет сделано много лишних присваиваний.

• Нарушение порядка: неверная работа с указателями с двух сторон (левый и правый). Если менять местами первый встречный ноль с последним ненулевым элементом, нарушится относительный порядок чисел. По условию задачи числа должны стоять так же, как и в оригинале.

• Ошибки с индексами: классическое место для багов. Легко запутаться, нужно ли инкрементировать указатели до или после обмена, и не выйдет ли индекс за границы массива на последней итерации.

Идея решения:

Мы будем использовать подход двух указателей, которые двигаются по массиву с разной скоростью. Первый указатель ("быстрый") перебирает все элементы по порядку, а второй ("медленный") указывает на позицию, где должен стоять следующий ненулевой элемент.

Каждый раз, когда быстрый указатель находит число, не равное нулю, мы меняем его местами с элементом, на который смотрит медленный указатель. После этого медленный указатель сдвигается на одну позицию вправо. Таким образом, все ненулевые числа постепенно "выталкиваются" в начало массива в исходном порядке, а нули автоматически сдвигаются в конец.

Основные шаги:

1. Первый указатель i ставим в начало массива. Он будет отвечать за индекс ячейки, куда нужно переместить следующий найденный ненулевой элемент.

2. Вторым указателем j идем в цикле по массиву.

   • Если текущий элемент nums[j] не равен нулю, значит, его нужно перенести.
     • Меняем местами элементы nums[i] и nums[j]. Даже если они указывают на одно и то же число в начале, это сработает корректно.
     • Сдвигаем i вправо, подготавливая место для следующего числа.

3. Завершение цикла:

   • В итоге все ненулевые числа соберутся слева в правильном порядке, а нули сдвинутся вправо.

Вот как это работает на примере:

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

Изначально оба указателя равны i = 0, j = 0.

1. j = 0: nums[0] - это 0. Ничего не делаем.

   • Массив: [0, 1, 0, 3, 12], i = 0.

2. j = 1: nums[1] - это 1 (не ноль).

   • Меняем местами nums[i] и nums[j] (индексы 0 и 1).
   • Массив: [1, 0, 0, 3, 12].
   • Сдвигаем i вперед: i = 1.

3. j = 2: nums[2] - это 0. Пропускаем.

   • Массив: [1, 0, 0, 3, 12], i = 1.

4. j = 3: nums[3] - это 3 (не ноль).

   • Меняем местами nums[i] и nums[j] (индексы 1 и 3).
   • Массив: [1, 3, 0, 0, 12].
   • Сдвигаем i вперед: i = 2.

5. j = 4: nums[4] - это 12 (не ноль).

   • Меняем местами nums[i] и nums[j] (индексы 2 и 4).
   • Массив: [1, 3, 12, 0, 0].
   • Сдвигаем i вперед: i = 3.

Итог: цикл закончился, все ненулевые числа (1, 3, 12) стоят в начале и сохранили свой порядок, а нули сдвинуты в конец.

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

Временная сложность

Мы используем один цикл, который проходит по массиву от начала до конца ровно один раз. Таким образом, получаем временную сложность O(n).

Пространственная сложность

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

Код решения

Приведем код решения.

func moveZeroes(nums []int) {
    i := 0
    for j := 0; j < len(nums); j++ {
        if nums[j] != 0 {
            nums[i], nums[j] = nums[j], nums[i]
            i++
        }
    }
}

Итоги

Подведем краткие итоги по задаче:

1. Проверка базы. Это классический фильтр на понимание работы двух указателей для модификации на месте.

2. Элегантность. Умение решить задачу за один проход без создания лишних массивов отличает опытного разработчика от новичка.

3. Универсальность. Этот паттерн встречается в десятках более сложных задач от обработки строк до поиска циклов в списках.