---
title: "Преобразование массива на месте"
url: https://algopath.pro/ru/patterns/in-place-array
language: ru
summary: "Индекс записи идёт следом за индексом чтения по одному буферу. Назад копируется только нужное, второй массив не создаётся."
updated: 2026-08-24
---

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

Индекс записи идёт следом за индексом чтения по одному буферу. Назад копируется только нужное, второй массив не создаётся.

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

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

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

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

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

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

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

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

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

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

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

- **Два указателя (в одну сторону)** - Пара медленный и быстрый это один из способов переписать буфер. Работа на месте здесь цель, а не способ.
- **Хеш-множество / словарь** - Множество убирает дубликаты за проход, но хранит все ключи. Работа на месте нужна как раз ради памяти.
- **Элементарные сортировки (выбором, пузырьком, вставками)** - Сортировка вставками тоже правит один буфер, но меняет порядок. Здесь порядок выживших не меняется.
- **Префиксные суммы** - Префиксные суммы строят второй массив накопленных сумм. Именно его тут и хотят избежать.

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

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

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

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

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

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

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

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

```javascript
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;
}
```

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

- **Двигают write на каждом шаге** Тогда write и read совпадают и ничего не удаляется. write двигается только при сохранении.
- **Режут хвост прямо во время прохода** В остаточных ячейках лежат значения, до которых read ещё не дошёл. Обрезайте их после цикла.
- **Возвращают массив вместо длины** Такие задачи обычно просят новую длину. Сам буфер сохраняет исходный размер.
- **Сравнивают не с той ячейкой** Проверка дубликата смотрит на arr[write - 1], а не на arr[read - 1]. Ранние ячейки уже перезаписаны.

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

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

## JavaScript

```javascript
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
}
```

## Python

```python
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
```

## PHP

```php
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
}
```