Преобразование массива на месте

Преобразование массива на месте: как это работает?

Два индекса идут по одному массиву. read смотрит каждую ячейку, write помечает место для следующего нужного значения.

read сдвигается на каждом шаге цикла. write сдвигается только тогда, когда значение прошло проверку.

Нужное значение копируется в arr[write]. После этого write сдвигается на одну ячейку.

Лишнее значение оставляет write на месте. Следующее нужное перезапишет эту ячейку.

write никогда не обгоняет read, поэтому копия не портит непрочитанные данные. Одного буфера хватает именно поэтому.

В конце write хранит новую логическую длину. Ячейки после неё это остатки.

1. [1, 1, 2, 2, 3] write=1 read=1Убираем дубликаты в отсортированном массиве. Первое значение остаётся всегда.
2. [1, 1, 2, 2, 3] write=1 read=2arr[1] повторяет arr[0] и отбрасывается. write не двигается.
3. [1, 2, 2, 2, 3] write=2 read=3arr[2] новое, поэтому попадает в ячейку 1. write сдвигается.
4. [1, 2, 2, 2, 3] write=2 read=4arr[3] повторяет уже сохранённую двойку. Значение отбрасывается.
5. [1, 2, 3, 2, 3] write=3Тройка ложится в ячейку 2. Ответ это длина 3, хвост мусорный.

function inPlaceTransform(arr) {
    let write = 0;
    for (let read = 0; read < arr.length; read++) {
        if (shouldKeep(arr[read])) {
            arr[write] = arr[read];
            write++;
        }
    }
    return write; // new logical length
}

Преобразование массива на месте: разбор примера

Сдвинуть нули в конец

Дан массив чисел, все нули надо перенести в конец.

Порядок ненулевых значений должен сохраниться. Выделять второй массив нельзя.

Идите по массиву индексом чтения. Копируйте каждое ненулевое значение в arr[write] и двигайте write.

После прохода write указывает, где начинаются нули. Заполните нулями всё оттуда.

function moveZeroes(nums) {
    let write = 0;

    for (let read = 0; read < nums.length; read++) {
        if (nums[read] !== 0) {
            nums[write] = nums[read];
            write++;
        }
    }

    // everything from write onwards is a leftover slot
    while (write < nums.length) {
        nums[write] = 0;
        write++;
    }

    return nums;
}

Преобразование массива на месте: когда применять?

Эти формулировки в условии ведут сюда:

• •изменить массив на месте
• •O(1) дополнительной памяти
• •не выделять ещё один массив/строку
• •развернуть/повернуть/разбить/переместить элементы в одном буфере
• •вернуть новую длину после удаления дубликатов

Преобразование массива на месте: с чем путают?

• Два указателя (в одну сторону) (Two pointers (same direction)): Пара медленный и быстрый это один из способов переписать буфер. Работа на месте здесь цель, а не способ.
• Хеш-множество / словарь (Hash set / map): Множество убирает дубликаты за проход, но хранит все ключи. Работа на месте нужна как раз ради памяти.
• Элементарные сортировки (выбором, пузырьком, вставками) (Elementary sorts (selection, bubble, insertion)): Сортировка вставками тоже правит один буфер, но меняет порядок. Здесь порядок выживших не меняется.
• Префиксные суммы (Prefix sums): Префиксные суммы строят второй массив накопленных сумм. Именно его тут и хотят избежать.

Преобразование массива на месте: частые ошибки

• Двигают write на каждом шаге

  Тогда write и read совпадают и ничего не удаляется. write двигается только при сохранении.

• Режут хвост прямо во время прохода

  В остаточных ячейках лежат значения, до которых read ещё не дошёл. Обрезайте их после цикла.

• Возвращают массив вместо длины

  Такие задачи обычно просят новую длину. Сам буфер сохраняет исходный размер.

• Сравнивают не с той ячейкой

  Проверка дубликата смотрит на arr[write - 1], а не на arr[read - 1]. Ранние ячейки уже перезаписаны.

Преобразование массива на месте: задачи с собеседований

• Удаление дубликатов из отсортированного массива: Оставляйте значение, только если оно отличается от arr[write - 1].
• Удаление элемента: Оставляйте всё, что не равно заданному значению.
• Сдвиг нулей: Скопируйте ненулевые вперёд, потом добейте хвост нулями.
• Сортировка цветов: Три индекса переписывают один буфер за один проход.
• Поворот массива: Разверните весь массив, потом разверните каждую из двух частей.
• Разворот строки: Меняйте местами с обоих концов внутрь без нового буфера.
• Удаление дубликатов из отсортированного массива II: Оставляйте значение, пока оно отличается от arr[write - 2].

Преобразование массива на месте: сложность по времени и памяти

O(n)

n до 1e6 и один проход дают O(n) времени. Память остаётся O(1), потому что ничего не выделяется.