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

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

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

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

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

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

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

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

Источники: Wikipedia (англ.): In-place algorithm

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
}

declare function shouldKeep(value: number): boolean;

function inPlaceTransform(arr: number[]): number {
    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
}

def in_place_transform(arr):
    write = 0
    for read in range(len(arr)):
        if should_keep(arr[read]):
            arr[write] = arr[read]
            write += 1
    return write  # new logical length

function inPlaceTransform(array &$arr): int {
    $write = 0;
    for ($read = 0; $read < count($arr); $read++) {
        if (shouldKeep($arr[$read])) {
            $arr[$write] = $arr[$read];
            $write++;
        }
    }
    return $write; // new logical length
}

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

    private static boolean shouldKeep(int value) {
        throw new UnsupportedOperationException("your rule here");
    }

    public static int InPlaceTransform(int[] arr) {
        int write = 0;
        for (int read = 0; read < arr.Length; read++) {
            if (ShouldKeep(arr[read])) {
                arr[write] = arr[read];
                write++;
            }
        }
        return write; // new logical length
    }

    private static bool ShouldKeep(int value) {
        throw new NotImplementedException("your rule here");
    }

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

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

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

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

Идите по массиву индексом чтения. Копируйте каждое ненулевое значение в 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) дополнительной памяти» или «не выделять ещё один массив/строку». Решение на нём обычно укладывается в O(n).

• •изменить массив на месте
• •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]. Ранние ячейки уже перезаписаны.

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

Паттерн «Преобразование массива на месте» решает такие задачи с собеседований: Удаление дубликатов из отсортированного массива, Удаление элемента, Сдвиг нулей, Сортировка цветов, Поворот массива, Разворот строки и Удаление дубликатов из отсортированного массива II.

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

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

У паттерна «Преобразование массива на месте» целевая сложность O(n).

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