Указатели в одном направлении

Теперь оба указателя идут слева направо, но выполняют разные роли. Разберём задачу: дан отсортированный массив, нужно записать его уникальные значения в начало того же массива и вернуть длину получившегося префикса.

Как выглядит полезный префикс после сжатия

Для [1, 1, 2, 2, 2, 5] функция должна вернуть 3, а первые три позиции должны стать [1, 2, 5]. Значения после позиции 3 не считаются частью ответа. Относительный порядок уникальных элементов нужно сохранить, дополнительный массив использовать нельзя.

Чем плохи отдельный результат и удаления из середины

Самое прямое решение строит новый массив: проходит по входу и добавляет значение, если его ещё нет в результате. Для отсортированного входа это O(n) времени, но O(n) дополнительной памяти, поэтому условие «на месте» не выполнено.

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

Где уже есть место для готового ответа

Во время чтения нам нужен только уже построенный уникальный префикс. Свободная позиция сразу после него находится в самом входном массиве, поэтому хранить второй массив или многократно сдвигать хвост не требуется.

Почему сортировка ставит дубликаты рядом

В отсортированном массиве одинаковые значения стоят подряд. Если текущий элемент равен последнему уже записанному уникальному значению, это дубликат. Если отличается, такого значения в уникальном префиксе ещё нет и его можно записать в следующую свободную позицию.

Что разделяют read и write

Перед обработкой позиции read выполняются два свойства:

1. диапазон [0, write) содержит все уникальные значения из уже обработанного диапазона [0, read) в исходном порядке;
2. write <= read, поэтому запись в values[write] не уничтожает ни одного ещё не прочитанного элемента.

read отвечает за чтение входа, а write — за границу готового ответа.

Читаем вход и расширяем уникальный префикс

1. Для пустого массива вернуть 0.
2. Считать первый элемент уже принятым и установить write = 1.
3. Провести read от индекса 1 до конца.
4. Если values[read] отличается от values[write - 1], скопировать его в values[write] и увеличить write.
5. Вернуть write; только префикс [0, write) является ответом.

Компактация на месте в двух языках

C++17

#include <cassert>
#include <iostream>
#include <vector>

std::size_t uniquePrefix(std::vector<int>& values) {
    if (values.empty()) {
        return 0;
    }

    std::size_t write = 1;
    for (std::size_t read = 1; read < values.size(); ++read) {
        if (values[read] != values[write - 1]) {
            values[write] = values[read];
            ++write;
        }
    }

    return write;
}

int main() {
    std::vector<int> values{1, 1, 2, 2, 2, 5};
    const std::size_t length = uniquePrefix(values);
    const std::vector<int> expected{1, 2, 5};

    assert(length == expected.size());
    for (std::size_t index = 0; index < length; ++index) {
        assert(values[index] == expected[index]);
    }

    std::vector<int> empty;
    assert(uniquePrefix(empty) == 0);
    std::cout << "OK\n";
}

Python 3

def unique_prefix(values: list[int]) -> int:
    if not values:
        return 0

    write = 1
    for read in range(1, len(values)):
        if values[read] != values[write - 1]:
            values[write] = values[read]
            write += 1

    return write


values = [1, 1, 2, 2, 2, 5]
length = unique_prefix(values)
assert length == 3
assert values[:length] == [1, 2, 5]

empty: list[int] = []
assert unique_prefix(empty) == 0
print("OK")

Один проход без дополнительного массива

read посещает каждый элемент ровно один раз: время O(n). Используются только два индекса: дополнительная память O(1). Изменение выполняется на месте; память самого входного массива в оценку не входит.

Корректность сравнения с последним записанным значением опирается на сортировку по неубыванию.

Пустой вход, один элемент и бесполезный хвост

• Пустой массив: нельзя обращаться к values[0], ответ 0.
• Один элемент: он образует уникальный префикс длины 1.
• Все элементы равны: write остаётся равным 1.
• Все элементы различны: write == read на каждом шаге, запись фактически идёт на то же место.
• Отрицательные значения и ноль не требуют отдельной логики.
• Хвост после возвращённой длины может содержать старые значения и не является частью результата.

Проверяем полностью равные и полностью разные входы

• [] → длина 0, префикс [].
• [7] → длина 1, префикс [7].
• [4, 4, 4] → длина 1, префикс [4].
• [1, 2, 3] → длина 3, префикс [1, 2, 3].
• [-2, -2, 0, 0, 5] → длина 3, префикс [-2, 0, 5].

Когда условие просит полезный префикс на месте

Условие просит изменить массив на месте, сохранить порядок подходящих элементов и вернуть длину полезного префикса. Частые формулировки: «удалить дубликаты», «переместить подходящие элементы вперёд», «отфильтровать на месте».

Почему несортированным данным нужна дополнительная память

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

Может ли запись уничтожить непрочитанный элемент

Вопрос. Может ли запись в values[write] затереть элемент, который read ещё не видел?

Ответ. Нет. Всегда write <= read. Если индексы равны, элемент переписывается самим собой; если write < read, запись идёт только в уже обработанную часть. Позиции правее read не меняются.

Почему сравниваем с последним записанным значением

Вопрос. Почему после возврата длины нельзя считать весь массив очищенным от дубликатов?

Ответ. Алгоритм гарантирует содержимое только диапазона [0, write). Он не удаляет физические ячейки и не обязан очищать хвост. Например, после обработки [1, 1, 2] массив может выглядеть как [1, 2, 2], но ответом являются лишь первые две позиции.

Прослеживаем границу уникального ответа

Задание. Измените массив на месте так, чтобы все ненулевые элементы сохранили порядок и оказались впереди, а оставшиеся позиции были заполнены нулями. Для [0, 1, 0, 3, 12] нужен результат [1, 3, 12, 0, 0].

Подсказки. Пусть read просматривает каждый элемент. При ненулевом значении запишите его в values[write] и увеличьте write. После сканирования заполните диапазон от write до конца нулями.

Проверка инварианта. Перед каждым шагом [0, write) должен содержать все ненулевые элементы уже просмотренного префикса в исходном порядке.

Самостоятельная задача о фильтрации на месте

Задача 1

Удалите из массива на месте все вхождения заданного значения, сохранив относительный порядок остальных элементов. Верните длину полезного префикса; содержимое хвоста не определяется. Реализуйте одинаковый контракт на C++17 и Python и оцените сложность.

Разные роли указателей дают безопасную запись

Два сонаправленных указателя разделяют чтение и запись. read не пропускает вход, а write поддерживает точную границу уже построенного ответа; сортировка делает проверку дубликата локальной.