Перестроить массив, не заводя второй

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

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

Возьми первый тест, [0, 1, 0, 3]. Ответ должен быть [1, 3, 0, 0], и второй массив для этого заводить нельзя.

Поэтому работаешь в тех же четырёх ячейках. Одна переменная, write, помнит, в какую ячейку пойдёт следующее число, которое ты оставляешь. Сначала это ячейка 0. Вторая переменная, read, просматривает ячейки по одной слева направо. Когда read находит число, не равное 0, ты копируешь его в ячейку write и сдвигаешь write на одну ячейку вправо. Так 1 попадает в ячейку 0, а 3 в ячейку 1. Потом в ячейки 2 и 3 записываешь нули. Те же четыре ячейки теперь хранят [1, 3, 0, 0], и лишняя память не понадобилась. Ради этой сэкономленной памяти и нужен весь урок.

«На месте» значит, что ты правишь исходные ячейки напрямую и почти не тратишь лишнюю память. Большинство таких задач решают два приёма. В обоих есть указатель: так называют переменную, которая хранит номер ячейки.

Два указателя с концов (чтобы развернуть массив или поменять элементы местами). Указатель lo стоит в начале, указатель hi в конце. Меняешь местами две ячейки, на которые они указывают. Потом сдвигаешь оба на шаг навстречу друг другу. Останавливаешься, когда они встретятся.

Указатель записи (чтобы сдвинуть или удалить элементы). Медленный указатель write помнит, куда положить следующий оставляемый элемент. Быстрый указатель read проходит весь массив. Каждый раз, когда read находит элемент, который нужно оставить, ты копируешь его в ячейку write и сдвигаешь write на шаг вперёд.

Проследим «нули в конец» на [0, 1, 0, 3]. Читаем 0: пропускаем. Читаем 1: оставляем, пишем его в ячейку 0, массив стал [1, 1, 0, 3], write стал 1. Читаем 0: пропускаем. Читаем 3: оставляем, пишем в ячейку 1, массив стал [1, 3, 0, 3], write стал 2. Числа, которые надо оставить, уже стоят в начале. В ячейках 2 и 3 остались старые значения, их заполняем нулями: [1, 3, 0, 0]. Готово, второй массив не понадобился.

Время O(n): один проход по массиву. Память O(1): пара переменных под индексы и одна временная ячейка для обмена. Ничего из этого не растёт вместе с массивом. Новый массив стоил бы O(n) лишней памяти, а здесь её тратить нельзя.

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

Перед сохранением лога (журнала событий программы) из него вычищают личные данные, и делают это без копии большого буфера (участка памяти под данные). Буфер ввода-вывода приводят к нужному виду на месте. Сообщение укладывают в сетевой буфер фиксированного размера. Обслуживают кольцевой буфер: буфер постоянного размера, который заполняется по кругу. Во всех этих случаях памяти мало или один буфер используют заново для каждого запроса. Свежая копия там лишняя, и указатель записи помогает без неё обойтись.